mruby/src/string.c at master · mruby/mruby · GitHub

History

4505 lines (4120 loc) · 134 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

** string.c - String class

** See Copyright Notice in mruby.h

#ifdef _MSC_VER

# define _CRT_NONSTDC_NO_DEPRECATE

# define WIN32_LEAN_AND_MEAN

#endif

#include <mruby.h>

#include <mruby/array.h>

#include <mruby/class.h>

#include <mruby/range.h>

#include <mruby/string.h>

#include <mruby/numeric.h>

#include <mruby/internal.h>

#include <string.h>

typedef struct mrb_shared_string {

int refcnt;

mrb_int capa;

/* Offset past the last byte any sharer can see. Bytes at or above it are

dead to every sharer, so a writer may use them in place (str_modify_cat).

Only grows, as sharers are added. */

mrb_int reserved;

char *ptr;

} mrb_shared_string;

const char mrb_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";

#define mrb_obj_alloc_string(mrb) MRB_OBJ_ALLOC((mrb), MRB_TT_STRING, (mrb)->string_class)

#ifndef MRB_STR_LENGTH_MAX

#if defined(__linux__) || defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__)

#define MRB_STR_LENGTH_MAX 0

#else

#define MRB_STR_LENGTH_MAX 1048576

#endif

static void

str_check_length(mrb_state *mrb, mrb_int len)

{

if (len < 0 || len == MRB_INT_MAX) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "negative (or overflowed) string size");

}

#if MRB_STR_LENGTH_MAX != 0

if (len > MRB_STR_LENGTH_MAX-1) {

mrb_raisef(mrb, E_ARGUMENT_ERROR, "string too long (len=%i max=" MRB_STRINGIZE(MRB_STR_LENGTH_MAX) ")", len);

}

#endif

}

mrb_bool

mrb_strcasecmp_p(const char *s1, mrb_int len1, const char *s2, mrb_int len2)

{

if (len1 != len2) return FALSE;

const char *e1 = s1 + len1;

while (s1 < e1) {

if (*s1 != *s2 && TOUPPER(*s1) != TOUPPER(*s2)) return FALSE;

s1++;

s2++;

}

return TRUE;

}

static struct RString*

str_init_normal_capa(mrb_state *mrb, struct RString *s,

const char *p, mrb_int len, mrb_int capa)

{

str_check_length(mrb, capa);

char *dst = (char*)mrb_malloc(mrb, capa + 1);

if (p) memcpy(dst, p, len);

dst[len] = '\0';

s->as.heap.ptr = dst;

s->as.heap.len = len;

s->as.heap.aux.capa = capa;

RSTR_SET_TYPE(s, NORMAL);

return s;

}

static struct RString*

str_init_normal(mrb_state *mrb, struct RString *s, const char *p, mrb_int len)

{

return str_init_normal_capa(mrb, s, p, len, len);

}

static struct RString*

str_init_embed(struct RString *s, const char *p, mrb_int len)

{

mrb_assert(len >= 0);

if (p) memcpy(RSTR_EMBED_PTR(s), p, len);

RSTR_EMBED_PTR(s)[len] = '\0';

RSTR_SET_TYPE(s, EMBED);

RSTR_SET_EMBED_LEN(s, len);

return s;

}

static struct RString*

str_init_nofree(struct RString *s, const char *p, mrb_int len)

{

s->as.heap.ptr = (char*)p;

s->as.heap.len = len;

s->as.heap.aux.capa = 0; /* nofree */

RSTR_SET_TYPE(s, NOFREE);

return s;

}

static struct RString*

str_init_shared(mrb_state *mrb, const struct RString *orig, struct RString *s, mrb_shared_string *shared)

{

if (shared) {

mrb_int end = (mrb_int)(orig->as.heap.ptr - shared->ptr) + orig->as.heap.len;

if (shared->reserved < end) shared->reserved = end;

shared->refcnt++;

}

else {

shared = (mrb_shared_string*)mrb_malloc(mrb, sizeof(mrb_shared_string));

shared->refcnt = 1;

shared->ptr = orig->as.heap.ptr;

shared->capa = orig->as.heap.aux.capa;

shared->reserved = orig->as.heap.len;

}

s->as.heap.ptr = orig->as.heap.ptr;

s->as.heap.len = orig->as.heap.len;

s->as.heap.aux.shared = shared;

RSTR_SET_TYPE(s, SHARED);

return s;

}

static struct RString*

str_init_fshared(const struct RString *orig, struct RString *s, struct RString *fshared)

{

s->as.heap.ptr = orig->as.heap.ptr;

s->as.heap.len = orig->as.heap.len;

s->as.heap.aux.fshared = fshared;

RSTR_SET_TYPE(s, FSHARED);

return s;

}

static struct RString*

str_init_modifiable(mrb_state *mrb, struct RString *s, const char *p, mrb_int len)

{

if (RSTR_EMBEDDABLE_P(len)) {

return str_init_embed(s, p, len);

}

return str_init_normal(mrb, s, p, len);

}

static struct RString*

str_new_static(mrb_state *mrb, const char *p, mrb_int len)

{

if (RSTR_EMBEDDABLE_P(len)) {

return str_init_embed(mrb_obj_alloc_string(mrb), p, len);

}

return str_init_nofree(mrb_obj_alloc_string(mrb), p, len);

}

static struct RString*

str_new(mrb_state *mrb, const char *p, mrb_int len)

{

str_check_length(mrb, len);

if (RSTR_EMBEDDABLE_P(len)) {

return str_init_embed(mrb_obj_alloc_string(mrb), p, len);

}

if (p && mrb_ro_data_p(p)) {

return str_init_nofree(mrb_obj_alloc_string(mrb), p, len);

}

return str_init_normal(mrb, mrb_obj_alloc_string(mrb), p, len);

}

* @param mrb The mruby state.

* @param capa The desired capacity of the new string.

* @return A new mruby string with the specified capacity.

* Creates a new mruby string with a given initial capacity.

* The string is initially empty.

MRB_API mrb_value

mrb_str_new_capa(mrb_state *mrb, mrb_int capa)

{

struct RString *s = mrb_obj_alloc_string(mrb);

if (RSTR_EMBEDDABLE_P(capa)) {

s = str_init_embed(s, NULL, 0);

}

else {

s = str_init_normal_capa(mrb, s, NULL, 0, capa);

}

return mrb_obj_value(s);

}

static void

resize_capa(mrb_state *mrb, struct RString *s, mrb_int capacity)

{

if (RSTR_EMBED_P(s)) {

if (!RSTR_EMBEDDABLE_P(capacity)) {

str_init_normal_capa(mrb, s, RSTR_EMBED_PTR(s), RSTR_EMBED_LEN(s), capacity);

}

else {

str_check_length(mrb, capacity);

s->as.heap.ptr = (char*)mrb_realloc(mrb, RSTR_PTR(s), capacity+1);

s->as.heap.aux.capa = (mrb_ssize)capacity;

}

* @param mrb The mruby state.

* @param p A pointer to the C string to copy.

* @param len The length of the C string.

* @return A new mruby string containing the copied C string.

* Creates a new mruby string from a C string and a specified length.

* If `p` is NULL, an empty string is created.

MRB_API mrb_value

mrb_str_new(mrb_state *mrb, const char *p, mrb_int len)

{

return mrb_obj_value(str_new(mrb, p, len));

}

* @param mrb The mruby state.

* @param p A pointer to the null-terminated C string to copy.

* @return A new mruby string containing the copied C string.

* Creates a new mruby string from a null-terminated C string.

* If `p` is NULL, an empty string is created.

MRB_API mrb_value

mrb_str_new_cstr(mrb_state *mrb, const char *p)

{

struct RString *s;

mrb_int len;

if (p) {

len = strlen(p);

}

else {

len = 0;

}

s = str_new(mrb, p, len);

return mrb_obj_value(s);

}

* @param mrb The mruby state.

* @param p A pointer to the static C string.

* @param len The length of the static C string.

* @return A new mruby string referencing the static C string.

* Creates a new mruby string that directly references a static C string.

* The C string is not copied and must remain valid for the lifetime of the mruby string.

* This is typically used for string literals.

MRB_API mrb_value

mrb_str_new_static(mrb_state *mrb, const char *p, mrb_int len)

{

struct RString *s = str_new_static(mrb, p, len);

return mrb_obj_value(s);

}

static void

str_decref(mrb_state *mrb, mrb_shared_string *shared)

{

shared->refcnt--;

if (shared->refcnt == 0) {

mrb_free(mrb, shared->ptr);

mrb_free(mrb, shared);

}

static void

str_unshare_buffer(mrb_state *mrb, struct RString *s)

{

if (RSTR_SHARED_P(s)) {

mrb_shared_string *shared = s->as.heap.aux.shared;

if (shared->refcnt == 1 && s->as.heap.ptr == shared->ptr) {

s->as.heap.aux.capa = shared->capa;

s->as.heap.ptr[s->as.heap.len] = '\0';

RSTR_SET_TYPE(s, NORMAL);

mrb_free(mrb, shared);

}

else {

str_init_modifiable(mrb, s, s->as.heap.ptr, s->as.heap.len);

str_decref(mrb, shared);

}

else if (RSTR_NOFREE_P(s) || RSTR_FSHARED_P(s)) {

str_init_modifiable(mrb, s, s->as.heap.ptr, s->as.heap.len);

}

static void

check_null_byte(mrb_state *mrb, struct RString *str)

{

const char *p = RSTR_PTR(str);

if (p && memchr(p, '\0', RSTR_LEN(str))) {

mrb_raise(mrb, E_ARGUMENT_ERROR, "string contains null byte");

}

void

mrb_gc_free_str(mrb_state *mrb, struct RString *str)

{

if (RSTR_EMBED_P(str))

/* no code */;

else if (RSTR_SHARED_P(str))

str_decref(mrb, str->as.heap.aux.shared);

else if (!RSTR_NOFREE_P(str) && !RSTR_FSHARED_P(str))

mrb_free(mrb, str->as.heap.ptr);

}

#if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \

defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD64) || \

defined(__powerpc64__) || defined(__POWERPC__) || defined(__aarch64__) || \

defined(__mc68020__)

# define ALIGNED_WORD_ACCESS 0

#else

# define ALIGNED_WORD_ACCESS 1

#endif

#ifdef MRB_64BIT

#define bitint uint64_t

#define MASK01 0x0101010101010101ull

#else

#define bitint uint32_t

#define MASK01 0x01010101ul

#endif

/* Encode a Unicode codepoint to UTF-8 bytes, into a buffer of at least four.

Returns the number of bytes written (1-4), or 0 for a value outside

U+0000..U+10FFFF, which spells no character. The value arrives as an

mrb_int so that a negative one and one past the range are both this

function's answer to give; a caller reporting them differs only in which

exception it raises, and each raises what CRuby raises there.

A surrogate does encode. What CRuby writes for one is what mruby writes:

sprintf("%c", 0xD800) and [0xD800].pack("U") both yield ED A0 80 there.

Reading those bytes back is a separate question, and mrb_utf8len() answers

it by RFC 3629, under which a surrogate spells nothing. So what this writes

is deliberately wider than what that reads, and a string built from one is

valid_encoding? == false. */

mrb_int

mrb_utf8_to_buf(char *buf, mrb_int cp)

{

if (cp < 0) {

return 0;

}

else if (cp < 0x80) {

buf[0] = (char)cp;

return 1;

}

else if (cp < 0x800) {

buf[0] = (char)(0xC0 | (cp >> 6));

buf[1] = (char)(0x80 | (cp & 0x3F));

return 2;

}

else if (cp < 0x10000) {

buf[0] = (char)(0xE0 | (cp >> 12));

buf[1] = (char)(0x80 | ((cp >> 6) & 0x3F));

buf[2] = (char)(0x80 | (cp & 0x3F));

return 3;

}

else if (cp <= 0x10FFFF) {

buf[0] = (char)(0xF0 | (cp >> 18));

buf[1] = (char)(0x80 | ((cp >> 12) & 0x3F));

buf[2] = (char)(0x80 | ((cp >> 6) & 0x3F));

buf[3] = (char)(0x80 | (cp & 0x3F));

return 4;

}

return 0; /* above U+10FFFF */

}

/* UTF-8: what a run of bytes spells, and what a string holds character by

character. Only a build that indexes strings by character has to answer

either, so a build without MRB_UTF8_STRING carries none of it. */

#ifdef MRB_UTF8_STRING

#define utf8_islead(c) ((unsigned char)((c)&0xc0) != 0x80)

/* the byte length a lead byte claims, read only through mrb_utf8len() */

static const char mrb_utf8len_table[] = {

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 3, 4, 0

};

mrb_int

mrb_utf8len(const char* p, const char* e)

{

mrb_int len = mrb_utf8len_table[(unsigned char)p[0] >> 3];

if (len > e - p) return 1;

switch (len) {

case 0:

return 1;

case 4:

if (utf8_islead(p[3])) return 1;

case 3:

if (utf8_islead(p[2])) return 1;

case 2:

if (utf8_islead(p[1])) return 1;

}

/* Reject overlong sequences, UTF-16 surrogates, and code points above

U+10FFFF (RFC 3629, Unicode D93b). */

switch ((unsigned char)p[0]) {

case 0xC0: case 0xC1: /* overlong (< U+0080) */

return 1;

case 0xE0: /* overlong (< U+0800) */

if ((unsigned char)p[1] < 0xA0) return 1;

break;

case 0xED: /* surrogate (U+D800..U+DFFF) */

if ((unsigned char)p[1] > 0x9F) return 1;

break;

case 0xF0: /* overlong (< U+10000) */

if ((unsigned char)p[1] < 0x90) return 1;

break;

case 0xF4: /* above U+10FFFF */

if ((unsigned char)p[1] > 0x8F) return 1;

break;

case 0xF5: case 0xF6: case 0xF7: /* above U+10FFFF */

return 1;

}

return len;

}

/* The byte the character covering `p` starts at, or `p` itself when `p` is

already a character boundary. A continuation byte belongs to the character

that reaches it; one that no lead byte reaches belongs to none and stands as

a character of its own. Whether a lead byte reaches is mrb_utf8len()'s

answer, so the boundaries found here are the ones the character count is

taken over. Reading back three bytes covers it, since nothing longer than

four bytes spells a character. */

const char*

mrb_utf8_char_head(const char *beg, const char *p, const char *end)

{

if (p >= end || utf8_islead(p[0])) return p;

for (mrb_int back = 1; back <= 3 && back <= p - beg; back++) {

const char *lead = p - back;

if (!utf8_islead(lead[0])) continue; /* another continuation byte */

return mrb_utf8len(lead, end) > back ? lead : p;

}

return p;

}

/* Decode a UTF-8 character and return its codepoint.

*lenp is set to the byte length consumed. mrb_utf8len() answers 1 for every

sequence it rejects, so those consume a single byte and come back as the

lead byte itself. */

uint32_t

mrb_utf8_decode(const char *p, const char *e, mrb_int *lenp)

{

uint8_t c = (uint8_t)p[0];

uint32_t cp;

mrb_int n = mrb_utf8len(p, e);

*lenp = n;

switch (n) {

case 2:

cp = (c & 0x1f) << 6;

cp |= ((uint8_t)p[1] & 0x3f);

return cp;

case 3:

cp = (c & 0x0f) << 12;

cp |= ((uint8_t)p[1] & 0x3f) << 6;

cp |= ((uint8_t)p[2] & 0x3f);

return cp;

case 4:

cp = (c & 0x07) << 18;

cp |= ((uint8_t)p[1] & 0x3f) << 12;

cp |= ((uint8_t)p[2] & 0x3f) << 6;

cp |= ((uint8_t)p[3] & 0x3f);

return cp;

default:

return c; /* ASCII, or invalid/truncated byte returned as-is */

}

#define NOASCII(c) ((c) & 0x80)

#ifdef SIMPLE_SEARCH_NONASCII

/* the naive implementation. define SIMPLE_SEARCH_NONASCII, */

/* if you need it for any constraint (e.g. code size). */

static const char*

search_nonascii(const char* p, const char *e)

{

for (; p < e; ++p) {

if (NOASCII(*p)) return p;

}

return e;

}

#elif defined(__SSE2__)

# include <emmintrin.h>

static inline const char *

search_nonascii(const char *p, const char *e)

{

if (sizeof(__m128i) < (size_t)(e - p)) {

if (!_mm_movemask_epi8(_mm_loadu_si128((__m128i const*)p))) {

const intptr_t lowbits = sizeof(__m128i) - 1;

const __m128i *s, *t;

s = (const __m128i*)(~lowbits & ((intptr_t)p + lowbits));

t = (const __m128i*)(~lowbits & (intptr_t)e);

for (; s < t; ++s) {

if (_mm_movemask_epi8(_mm_load_si128(s))) break;

}

p = (const char *)s;

}

switch (e - p) {

default:

case 15: if (NOASCII(*p)) return p; ++p;

case 14: if (NOASCII(*p)) return p; ++p;

case 13: if (NOASCII(*p)) return p; ++p;

case 12: if (NOASCII(*p)) return p; ++p;

case 11: if (NOASCII(*p)) return p; ++p;

case 10: if (NOASCII(*p)) return p; ++p;

case 9: if (NOASCII(*p)) return p; ++p;

case 8: if (NOASCII(*p)) return p; ++p;

case 7: if (NOASCII(*p)) return p; ++p;

case 6: if (NOASCII(*p)) return p; ++p;

case 5: if (NOASCII(*p)) return p; ++p;

case 4: if (NOASCII(*p)) return p; ++p;

case 3: if (NOASCII(*p)) return p; ++p;

case 2: if (NOASCII(*p)) return p; ++p;

case 1: if (NOASCII(*p)) return p; ++p;

if (NOASCII(*p)) return p;

case 0: break;

}

return e;

}

#else

static const char*

search_nonascii(const char *p, const char *e)

{

ptrdiff_t byte_len = e - p;

const char *be = p + sizeof(bitint) * (byte_len / sizeof(bitint));

for (; p < be; p+=sizeof(bitint)) {

bitint t0;

memcpy(&t0, p, sizeof(bitint));

const bitint t1 = t0 & (MASK01*0x80);

if (t1) {

e = p + sizeof(bitint)-1;

byte_len = sizeof(bitint)-1;

break;

}

switch (byte_len % sizeof(bitint)) {

#ifdef MRB_64BIT

case 7: if (e[-7]&0x80) return e-7;

case 6: if (e[-6]&0x80) return e-6;

case 5: if (e[-5]&0x80) return e-5;

case 4: if (e[-4]&0x80) return e-4;

#endif

case 3: if (e[-3]&0x80) return e-3;

case 2: if (e[-2]&0x80) return e-2;

case 1: if (e[-1]&0x80) return e-1;

}

return e;

}

#endif /* SIMPLE_SEARCH_NONASCII */

#if defined(__GNUC__) || __has_builtin(__builtin_popcount)

# ifdef MRB_64BIT

# define popcount(x) __builtin_popcountll(x)

# else

# define popcount(x) __builtin_popcountl(x)

# endif

#else

#define POPC_SHIFT (8 * sizeof(bitint) - 8)

static inline uint32_t popcount(bitint x)

{

x = (x & (MASK01*0x55)) + ((x >> 1) & (MASK01*0x55));

x = (x & (MASK01*0x33)) + ((x >> 2) & (MASK01*0x33));

x = (x & (MASK01*0x0F)) + ((x >> 4) & (MASK01*0x0F));

return (uint32_t)((x * MASK01) >> POPC_SHIFT);

}

#endif

/* Counts characters, and when `validp` is given also reports whether every

sequence decoded as one character. The walk stops at the first broken

sequence, so the returned count is a character count only while `*validp`

stays TRUE. */

static mrb_int

utf8_strlen_check(const char *str, mrb_int byte_len, mrb_bool *validp)

{

const char *p = str;

const char *e = str + byte_len;

mrb_int len = 0;

while (p < e) {

const char *np = search_nonascii(p, e);

len += np - p;

if (np == e) break;

p = np;

while (p < e && NOASCII(*p)) {

mrb_int clen = mrb_utf8len(p, e);

/* mrb_utf8len() answers 1 for a byte that leads no valid sequence. The

byte here is known to be non-ASCII, so a length of 1 means the string

carries a byte that stands for no character. */

if (validp && clen == 1) {

*validp = FALSE;

return len;

}

p += clen;

len++;

}

return len;

}

mrb_int

mrb_utf8_strlen(const char *str, mrb_int byte_len)

{

return utf8_strlen_check(str, byte_len, NULL);

}

/* count the characters of a string */

mrb_int

mrb_str_char_len(mrb_state *mrb, mrb_value str)

{

(void)mrb;

struct RString *s = mrb_str_ptr(str);

mrb_int byte_len = RSTR_LEN(s);

/* A single-byte string has one position per byte, which is what

mrb_str_char_to_byte() and mrb_str_byte_to_char() already answer for it.

Asked here only where the string stands, the same string was measured as

UTF-8 and reported a length its own indexing did not agree with.

Nothing is recorded on the way out. A string of nothing but ASCII carries

that already, and a byte-read one returns here because of how it is read

rather than because of what its bytes are: 7BIT would be a claim about

bytes nothing has looked at, and force_encoding() can take the byte

reading away again and leave the claim standing. */

if (RSTR_SINGLE_BYTE_P(s)) {

return byte_len;

}

else {

const char *p = RSTR_PTR(s);

const char *e = p + byte_len;

const char *np = search_nonascii(p, e);

/* Every character a non-ASCII byte begins spells two bytes or more, and a

non-ASCII byte that begins none spells no character at all, so a string

holds one character per byte exactly when every byte of it is ASCII.

Counts that come out equal do not say that: a byte spelling no character

is counted as one too, so a string of them set the flag as well, and the

readers of it went on to hand those bytes back as characters. */

if (np == e) {

RSTR_CODERANGE_SET(s, MRB_STR_CODERANGE_7BIT);

return byte_len;

}

mrb_int utf8_len = (mrb_int)(np - p) + mrb_utf8_strlen(np, (mrb_int)(e - np));

mrb_assert(utf8_len <= byte_len);

return utf8_len;

}

/* whether a string's bytes read as the encoding it is taken to have */

mrb_bool

mrb_str_valid_encoding_p(mrb_state *mrb, mrb_value str)

{

(void)mrb;

struct RString *s = mrb_str_ptr(str);

/* A byte-indexed string makes no such claim, so it is valid whatever its

bytes are. */

if (RSTR_BINARY_P(s)) return TRUE;

/* The walk below reads the whole string to answer either way, so a string

that has been walked already is answered off where it stands instead. A

string of one character per byte is one of those: it holds nothing but

ASCII, and ASCII reads as UTF-8 as it stands. This is what a string

counted before it is asked about comes in carrying. */

mrb_int cr = RSTR_CODERANGE(s);

if (cr == MRB_STR_CODERANGE_7BIT || cr == MRB_STR_CODERANGE_VALID) return TRUE;

if (cr == MRB_STR_CODERANGE_BROKEN) return FALSE;

mrb_int byte_len = RSTR_LEN(s);

mrb_bool valid = TRUE;

mrb_int utf8_len = utf8_strlen_check(RSTR_PTR(s), byte_len, &valid);

if (!valid) {

RSTR_CODERANGE_SET(s, MRB_STR_CODERANGE_BROKEN);

return FALSE;

}

RSTR_CODERANGE_SET(s, byte_len == utf8_len ? MRB_STR_CODERANGE_7BIT

: MRB_STR_CODERANGE_VALID);

return TRUE;

}

/* whether every byte of the string is ASCII. A walk that finds nothing else

has made the statement 7BIT makes, so the answer is left on the string for

the next asker to read off. */

static mrb_bool

str_ascii_p(struct RString *s)

{

if (RSTR_CODERANGE(s) == MRB_STR_CODERANGE_7BIT) return TRUE;

const char *p = RSTR_PTR(s);

const char *e = p + RSTR_LEN(s);

if (search_nonascii(p, e) != e) return FALSE;

RSTR_CODERANGE_SET(s, MRB_STR_CODERANGE_7BIT);

return TRUE;

}

/* Whether a character index into this string is already a byte index, asking

the bytes where the string does not say. RSTR_SINGLE_BYTE_P() reads what is

recorded and answers no for a string nothing has read yet, which sends every

later caller down the walking path however plain the bytes are. A string is

walked whole at most once here: the walk records what it finds, and it is

the same walk the character indexing would go on to do anyway. */

mrb_bool

mrb_str_single_byte_p(mrb_state *mrb, mrb_value str)

{

struct RString *s = mrb_str_ptr(str);

if (RSTR_CODERANGE(s) == MRB_STR_CODERANGE_UNKNOWN) {

mrb_str_valid_encoding_p(mrb, str);

}

return RSTR_SINGLE_BYTE_P(s);

}

/* map character index to byte offset index */

mrb_int

mrb_str_char_to_byte(mrb_state *mrb, mrb_value str, mrb_int off, mrb_int idx)

{

(void)mrb;

struct RString *s = mrb_str_ptr(str);

if (RSTR_SINGLE_BYTE_P(s)) {

return idx;

}

const char *o = RSTR_PTR(s);

const char *p0 = o + off;

const char *p = p0;

const char *e = o + RSTR_LEN(s);

mrb_int i = 0;

while (p<e && i<idx) {

if ((*p & 0x80) == 0) {

/* Every ASCII byte stands for a character of its own, so the run only

has to be followed as far as the index asks for. Reading to the end of

the string instead makes finding the character just past the head cost

what finding the last one does. */

const char *lim = (e - p) > (idx - i) ? p + (idx - i) : e;

const char *np = search_nonascii(p, lim);

i += np - p;

p = np;

}

else {

p += mrb_utf8len(p, e);

i++;

}

mrb_int len = (mrb_int)(p-p0);

if (i<idx) len++;

return len;

}

/* map byte offset to character index */

mrb_int

mrb_str_byte_to_char(mrb_state *mrb, mrb_value str, mrb_int bi)

{

(void)mrb;

struct RString *s = mrb_str_ptr(str);

if (bi < 0 || RSTR_LEN(s) < bi) return -1;

if (RSTR_SINGLE_BYTE_P(s)) {

return bi;

}

const char *p = RSTR_PTR(s);

const char *e = p + RSTR_LEN(s);

const char *pivot = p + bi;

mrb_int i = 0;

while (p < pivot) {

if ((*p & 0x80) == 0) {

const char *np = search_nonascii(p, pivot);

i += np - p;

p = np;

}

else {

p += mrb_utf8len(p, e);

i++;

}

if (p != pivot) return -1;

return i;

}

static mrb_int

str_index_str_by_char(mrb_state *mrb, mrb_value str, mrb_value sub, mrb_int pos)

{

/* see str_index_str() */

if (!mrb_str_valid_encoding_p(mrb, sub)) return -1;

const char *ptr = RSTRING_PTR(sub);

mrb_int len = RSTRING_LEN(sub);

if (pos > 0) {

pos = mrb_str_char_to_byte(mrb, str, 0, pos);

}

pos = mrb_str_index(mrb, str, ptr, len, pos);

if (pos > 0) {

pos = mrb_str_byte_to_char(mrb, str, pos);

}

return pos;

}

#else

/* a byte is a character here, so the count is the byte length and both

conversions are identity */

mrb_int

mrb_str_char_len(mrb_state *mrb, mrb_value str)

{

(void)mrb;

return RSTRING_LEN(str);

}

mrb_int

mrb_str_char_to_byte(mrb_state *mrb, mrb_value str, mrb_int off, mrb_int idx)

{

(void)mrb;

(void)str;

(void)off;

return idx;

}

mrb_int

mrb_str_byte_to_char(mrb_state *mrb, mrb_value str, mrb_int bi)

{

(void)mrb;

if (bi < 0 || RSTRING_LEN(str) < bi) return -1;

return bi;

}

#define str_index_str_by_char(mrb, str, sub, pos) str_index_str((mrb), (str), (sub), (pos))

/* a string is bytes here, with no encoding to disagree with */

mrb_bool

mrb_str_valid_encoding_p(mrb_state *mrb, mrb_value str)

{

(void)mrb;

(void)str;

return TRUE;

}

#define str_ascii_p(s) TRUE

#endif

/* memsearch_swar (SWAR stands for SIMD within a register) */

/* See https://en.wikipedia.org/wiki/SWAR */

/* The function is taken from http://0x80.pl/articles/simd-strfind.html */

/* The original source code is under 2-clause BSD license; see LEGAL file. */

/* The modifications:

* port from C++ to C

* returns mrb_int

* remove alignment issue

* support bigendian CPU

* fixed potential buffer overflow

static inline mrb_int

memsearch_swar(const char *xs, mrb_int m, const char *ys, mrb_int n)

{

#define MASK7f (MASK01*0x7f)

#define MASK80 (MASK01*0x80)

#if defined(MRB_ENDIAN_BIG)

#ifdef MRB_64BIT

#define MASKtop 0x8000000000000000ull

#else

#define MASKtop 0x80000000ul

#endif

#else

#define MASKtop 0x80

#endif

const bitint first = MASK01 * (uint8_t)xs[0];

const bitint last = MASK01 * (uint8_t)xs[m-1];

const char *s0 = ys;

const char *s1 = ys+m-1;

const mrb_int lim = n - m - (mrb_int)sizeof(bitint);

mrb_int i;

for (i=0; i < lim; i+=sizeof(bitint)) {

bitint t0, t1;

memcpy(&t0, s0+i, sizeof(bitint));

memcpy(&t1, s1+i, sizeof(bitint));

const bitint eq = (t0 ^ first) | (t1 ^ last);

bitint zeros = ((~eq & MASK7f) + MASK01) & (~eq & MASK80);

for (size_t j = 0; zeros; j++) {

if (zeros & MASKtop) {

const mrb_int idx = i + j;

const char* p = s0 + idx + 1;

if (memcmp(p, xs + 1, m - 2) == 0) {

return idx;

}

#if defined(MRB_ENDIAN_BIG)

zeros <<= 8;

#else

zeros >>= 8;

#endif

}

if (i+m < n) {

const char *p = s0;

const char *e = ys + n;

while (p<e) {

p = (const char*)memchr(p, *xs, e - p);

if (p == NULL || (e - p) < m) break;

if (memcmp(p+1, xs+1, m-1) == 0) return (mrb_int)(p - ys);

p++;

}

return -1;

}

static mrb_int

mrb_memsearch(const char *x, mrb_int m, const char *y, mrb_int n)

{

if (m > n) return -1;

else if (m == n) {

return memcmp(x, y, m) == 0 ? 0 : -1;

}

else if (m < 1) {

return 0;

}

else if (m == 1) {

const char *p = (const char*)memchr(y, *x, n);

if (p) return (mrb_int)(p - y);

return -1;

}

return memsearch_swar(x, m, y, n);

}

static void

str_share(mrb_state *mrb, struct RString *orig, struct RString *s)

{

size_t len = (size_t)orig->as.heap.len;

mrb_assert(!RSTR_EMBED_P(orig));

if (RSTR_NOFREE_P(orig)) {

str_init_nofree(s, orig->as.heap.ptr, len);

}

else if (RSTR_SHARED_P(orig)) {

str_init_shared(mrb, orig, s, orig->as.heap.aux.shared);

}

else if (RSTR_FSHARED_P(orig)) {

str_init_fshared(orig, s, orig->as.heap.aux.fshared);

}

else {

/* Spare capacity is kept, not trimmed: it lies above `reserved`, so

`orig` can still append into it without copying the buffer. */

str_init_shared(mrb, orig, s, NULL);

str_init_shared(mrb, orig, orig, s->as.heap.aux.shared);

}

* @param mrb The mruby state.

* @param str The original mruby string.

* @param beg The starting byte offset of the substring.

* @param len The length in bytes of the substring.

* @return A new mruby string representing the byte subsequence.

* Creates a new mruby string that is a subsequence of an existing string,

* based on byte offsets and length. This function may share the underlying

* buffer with the original string if possible.

mrb_value

mrb_str_byte_subseq(mrb_state *mrb, mrb_value str, mrb_int beg, mrb_int len)

{

struct RString *orig = mrb_str_ptr(str);

struct RString *s = mrb_obj_alloc_string(mrb);

View remainder of file in raw view

mruby/src/string.c at master · mruby/mruby · GitHub

Uh oh!

Expand file tree

Breadcrumbs

string.c

Latest commit

History

Breadcrumbs

string.c

File metadata and controls