1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=80:
3 *
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 *
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
11 *
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
15 * License.
16 *
17 * The Original Code is Mozilla Communicator client code, released
18 * March 31, 1998.
19 *
20 * The Initial Developer of the Original Code is
21 * Netscape Communications Corporation.
22 * Portions created by the Initial Developer are Copyright (C) 1998
23 * the Initial Developer. All Rights Reserved.
24 *
25 * Contributor(s):
26 *
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
38 *
39 * ***** END LICENSE BLOCK ***** */
41 /*
42 * JS string type implementation.
43 *
44 * In order to avoid unnecessary js_LockGCThing/js_UnlockGCThing calls, these
45 * native methods store strings (possibly newborn) converted from their 'this'
46 * parameter and arguments on the stack: 'this' conversions at argv[-1], arg
47 * conversions at their index (argv[0], argv[1]). This is a legitimate method
48 * of rooting things that might lose their newborn root due to subsequent GC
49 * allocations in the same native method.
50 */
51 #include "jsstddef.h"
52 #include <stdlib.h>
53 #include <string.h>
54 #include "jstypes.h"
55 #include "jsutil.h" /* Added by JSIFY */
56 #include "jshash.h" /* Added by JSIFY */
57 #include "jsprf.h"
58 #include "jsapi.h"
59 #include "jsarray.h"
60 #include "jsatom.h"
61 #include "jsbool.h"
62 #include "jscntxt.h"
63 #include "jsconfig.h"
64 #include "jsgc.h"
65 #include "jsinterp.h"
66 #include "jslock.h"
67 #include "jsnum.h"
68 #include "jsobj.h"
69 #include "jsopcode.h"
70 #include "jsregexp.h"
71 #include "jsstr.h"
73 #if JS_HAS_REPLACE_LAMBDA
74 #include "jsinterp.h"
75 #endif
77 #define JSSTRDEP_RECURSION_LIMIT 100
79 size_t
80 js_MinimizeDependentStrings(JSString *str, int level, JSString **basep)
81 {
82 JSString *base;
83 size_t start, length;
85 JS_ASSERT(JSSTRING_IS_DEPENDENT(str));
86 base = JSSTRDEP_BASE(str);
87 start = JSSTRDEP_START(str);
88 if (JSSTRING_IS_DEPENDENT(base)) {
89 if (level < JSSTRDEP_RECURSION_LIMIT) {
90 start += js_MinimizeDependentStrings(base, level + 1, &base);
91 } else {
92 do {
93 start += JSSTRDEP_START(base);
94 base = JSSTRDEP_BASE(base);
95 } while (JSSTRING_IS_DEPENDENT(base));
96 }
97 if (start == 0) {
98 JS_ASSERT(JSSTRING_IS_PREFIX(str));
99 JSPREFIX_SET_BASE(str, base);
100 } else if (start <= JSSTRDEP_START_MASK) {
101 length = JSSTRDEP_LENGTH(str);
102 JSSTRDEP_SET_START_AND_LENGTH(str, start, length);
103 JSSTRDEP_SET_BASE(str, base);
104 }
105 }
106 *basep = base;
107 return start;
108 }
110 jschar *
111 js_GetDependentStringChars(JSString *str)
112 {
113 size_t start;
114 JSString *base;
116 start = js_MinimizeDependentStrings(str, 0, &base);
117 JS_ASSERT(!JSSTRING_IS_DEPENDENT(base));
118 JS_ASSERT(start < base->length);
119 return base->chars + start;
120 }
122 jschar *
123 js_GetStringChars(JSString *str)
124 {
125 if (JSSTRING_IS_DEPENDENT(str) && !js_UndependString(NULL, str))
126 return NULL;
128 *js_GetGCThingFlags(str) &= ~GCF_MUTABLE;
129 return str->chars;
130 }
132 JSString *
133 js_ConcatStrings(JSContext *cx, JSString *left, JSString *right)
134 {
135 size_t rn, ln, lrdist, n;
136 jschar *rs, *ls, *s;
137 JSDependentString *ldep; /* non-null if left should become dependent */
138 JSString *str;
140 if (JSSTRING_IS_DEPENDENT(right)) {
141 rn = JSSTRDEP_LENGTH(right);
142 rs = JSSTRDEP_CHARS(right);
143 } else {
144 rn = right->length;
145 rs = right->chars;
146 }
147 if (rn == 0)
148 return left;
150 if (JSSTRING_IS_DEPENDENT(left) ||
151 !(*js_GetGCThingFlags(left) & GCF_MUTABLE)) {
152 /* We must copy if left does not own a buffer to realloc. */
153 ln = JSSTRING_LENGTH(left);
154 if (ln == 0)
155 return right;
156 ls = JSSTRING_CHARS(left);
157 s = (jschar *) JS_malloc(cx, (ln + rn + 1) * sizeof(jschar));
158 if (!s)
159 return NULL;
160 js_strncpy(s, ls, ln);
161 ldep = NULL;
162 } else {
163 /* We can realloc left's space and make it depend on our result. */
164 ln = left->length;
165 if (ln == 0)
166 return right;
167 ls = left->chars;
168 s = (jschar *) JS_realloc(cx, ls, (ln + rn + 1) * sizeof(jschar));
169 if (!s)
170 return NULL;
172 /* Take care: right could depend on left! */
173 lrdist = (size_t)(rs - ls);
174 if (lrdist < ln)
175 rs = s + lrdist;
176 left->chars = ls = s;
177 ldep = JSSTRDEP(left);
178 }
180 js_strncpy(s + ln, rs, rn);
181 n = ln + rn;
182 s[n] = 0;
183 str = js_NewString(cx, s, n, GCF_MUTABLE);
184 if (!str) {
185 /* Out of memory: clean up any space we (re-)allocated. */
186 if (!ldep) {
187 JS_free(cx, s);
188 } else {
189 s = JS_realloc(cx, ls, (ln + 1) * sizeof(jschar));
190 if (s)
191 left->chars = s;
192 }
193 } else {
194 /* Morph left into a dependent prefix if we realloc'd its buffer. */
195 if (ldep) {
196 JSPREFIX_SET_LENGTH(ldep, ln);
197 JSPREFIX_SET_BASE(ldep, str);
198 #ifdef DEBUG
199 {
200 JSRuntime *rt = cx->runtime;
201 JS_RUNTIME_METER(rt, liveDependentStrings);
202 JS_RUNTIME_METER(rt, totalDependentStrings);
203 JS_LOCK_RUNTIME_VOID(rt,
204 (rt->strdepLengthSum += (double)ln,
205 rt->strdepLengthSquaredSum += (double)ln * (double)ln));
206 }
207 #endif
208 }
209 }
211 return str;
212 }
214 /*
215 * May be called with null cx by js_GetStringChars, above; and by the jslock.c
216 * MAKE_STRING_IMMUTABLE file-local macro.
217 */
218 const jschar *
219 js_UndependString(JSContext *cx, JSString *str)
220 {
221 size_t n, size;
222 jschar *s;
224 if (JSSTRING_IS_DEPENDENT(str)) {
225 n = JSSTRDEP_LENGTH(str);
226 size = (n + 1) * sizeof(jschar);
227 s = (jschar *) (cx ? JS_malloc(cx, size) : malloc(size));
228 if (!s)
229 return NULL;
231 js_strncpy(s, JSSTRDEP_CHARS(str), n);
232 s[n] = 0;
233 str->length = n;
234 str->chars = s;
236 #ifdef DEBUG
237 if (cx) {
238 JSRuntime *rt = cx->runtime;
239 JS_RUNTIME_UNMETER(rt, liveDependentStrings);
240 JS_RUNTIME_UNMETER(rt, totalDependentStrings);
241 JS_LOCK_RUNTIME_VOID(rt,
242 (rt->strdepLengthSum -= (double)n,
243 rt->strdepLengthSquaredSum -= (double)n * (double)n));
244 }
245 #endif
246 }
248 return str->chars;
249 }
251 /*
252 * Forward declarations for URI encode/decode and helper routines
253 */
254 static JSBool
255 str_decodeURI(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
256 jsval *rval);
258 static JSBool
259 str_decodeURI_Component(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
260 jsval *rval);
262 static JSBool
263 str_encodeURI(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
264 jsval *rval);
266 static JSBool
267 str_encodeURI_Component(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
268 jsval *rval);
270 static uint32
271 Utf8ToOneUcs4Char(const uint8 *utf8Buffer, int utf8Length);
273 /*
274 * Contributions from the String class to the set of methods defined for the
275 * global object. escape and unescape used to be defined in the Mocha library,
276 * but as ECMA decided to spec them, they've been moved to the core engine
277 * and made ECMA-compliant. (Incomplete escapes are interpreted as literal
278 * characters by unescape.)
279 */
281 /*
282 * Stuff to emulate the old libmocha escape, which took a second argument
283 * giving the type of escape to perform. Retained for compatibility, and
284 * copied here to avoid reliance on net.h, mkparse.c/NET_EscapeBytes.
285 */
287 #define URL_XALPHAS ((uint8) 1)
288 #define URL_XPALPHAS ((uint8) 2)
289 #define URL_PATH ((uint8) 4)
291 static const uint8 urlCharType[256] =
292 /* Bit 0 xalpha -- the alphas
293 * Bit 1 xpalpha -- as xalpha but
294 * converts spaces to plus and plus to %20
295 * Bit 2 ... path -- as xalphas but doesn't escape '/'
296 */
297 /* 0 1 2 3 4 5 6 7 8 9 A B C D E F */
298 { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 0x */
299 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 1x */
300 0,0,0,0,0,0,0,0,0,0,7,4,0,7,7,4, /* 2x !"#$%&'()*+,-./ */
301 7,7,7,7,7,7,7,7,7,7,0,0,0,0,0,0, /* 3x 0123456789:;<=>? */
302 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, /* 4x @ABCDEFGHIJKLMNO */
303 7,7,7,7,7,7,7,7,7,7,7,0,0,0,0,7, /* 5X PQRSTUVWXYZ[\]^_ */
304 0,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, /* 6x `abcdefghijklmno */
305 7,7,7,7,7,7,7,7,7,7,7,0,0,0,0,0, /* 7X pqrstuvwxyz{\}~ DEL */
306 0, };
308 /* This matches the ECMA escape set when mask is 7 (default.) */
310 #define IS_OK(C, mask) (urlCharType[((uint8) (C))] & (mask))
312 /* See ECMA-262 15.1.2.4. */
313 JSBool
314 js_str_escape(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
315 {
316 JSString *str;
317 size_t i, ni, length, newlength;
318 const jschar *chars;
319 jschar *newchars;
320 jschar ch;
321 jsint mask;
322 jsdouble d;
323 const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7',
324 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
326 mask = URL_XALPHAS | URL_XPALPHAS | URL_PATH;
327 if (argc > 1) {
328 if (!js_ValueToNumber(cx, argv[1], &d))
329 return JS_FALSE;
330 if (!JSDOUBLE_IS_FINITE(d) ||
331 (mask = (jsint)d) != d ||
332 mask & ~(URL_XALPHAS | URL_XPALPHAS | URL_PATH))
333 {
334 char numBuf[12];
335 JS_snprintf(numBuf, sizeof numBuf, "%lx", (unsigned long) mask);
336 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
337 JSMSG_BAD_STRING_MASK, numBuf);
338 return JS_FALSE;
339 }
340 }
342 str = js_ValueToString(cx, argv[0]);
343 if (!str)
344 return JS_FALSE;
345 argv[0] = STRING_TO_JSVAL(str);
347 chars = JSSTRING_CHARS(str);
348 length = newlength = JSSTRING_LENGTH(str);
350 /* Take a first pass and see how big the result string will need to be. */
351 for (i = 0; i < length; i++) {
352 if ((ch = chars[i]) < 128 && IS_OK(ch, mask))
353 continue;
354 if (ch < 256) {
355 if (mask == URL_XPALPHAS && ch == ' ')
356 continue; /* The character will be encoded as '+' */
357 newlength += 2; /* The character will be encoded as %XX */
358 } else {
359 newlength += 5; /* The character will be encoded as %uXXXX */
360 }
362 /*
363 * This overflow test works because newlength is incremented by at
364 * most 5 on each iteration.
365 */
366 if (newlength < length) {
367 JS_ReportOutOfMemory(cx);
368 return JS_FALSE;
369 }
370 }
372 if (newlength >= ~(size_t)0 / sizeof(jschar)) {
373 JS_ReportOutOfMemory(cx);
374 return JS_FALSE;
375 }
377 newchars = (jschar *) JS_malloc(cx, (newlength + 1) * sizeof(jschar));
378 if (!newchars)
379 return JS_FALSE;
380 for (i = 0, ni = 0; i < length; i++) {
381 if ((ch = chars[i]) < 128 && IS_OK(ch, mask)) {
382 newchars[ni++] = ch;
383 } else if (ch < 256) {
384 if (mask == URL_XPALPHAS && ch == ' ') {
385 newchars[ni++] = '+'; /* convert spaces to pluses */
386 } else {
387 newchars[ni++] = '%';
388 newchars[ni++] = digits[ch >> 4];
389 newchars[ni++] = digits[ch & 0xF];
390 }
391 } else {
392 newchars[ni++] = '%';
393 newchars[ni++] = 'u';
394 newchars[ni++] = digits[ch >> 12];
395 newchars[ni++] = digits[(ch & 0xF00) >> 8];
396 newchars[ni++] = digits[(ch & 0xF0) >> 4];
397 newchars[ni++] = digits[ch & 0xF];
398 }
399 }
400 JS_ASSERT(ni == newlength);
401 newchars[newlength] = 0;
403 str = js_NewString(cx, newchars, newlength, 0);
404 if (!str) {
405 JS_free(cx, newchars);
406 return JS_FALSE;
407 }
408 *rval = STRING_TO_JSVAL(str);
409 return JS_TRUE;
410 }
411 #undef IS_OK
413 /* See ECMA-262 15.1.2.5 */
414 static JSBool
415 str_unescape(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
416 {
417 JSString *str;
418 size_t i, ni, length;
419 const jschar *chars;
420 jschar *newchars;
421 jschar ch;
423 str = js_ValueToString(cx, argv[0]);
424 if (!str)
425 return JS_FALSE;
426 argv[0] = STRING_TO_JSVAL(str);
428 chars = JSSTRING_CHARS(str);
429 length = JSSTRING_LENGTH(str);
431 /* Don't bother allocating less space for the new string. */
432 newchars = (jschar *) JS_malloc(cx, (length + 1) * sizeof(jschar));
433 if (!newchars)
434 return JS_FALSE;
435 ni = i = 0;
436 while (i < length) {
437 ch = chars[i++];
438 if (ch == '%') {
439 if (i + 1 < length &&
440 JS7_ISHEX(chars[i]) && JS7_ISHEX(chars[i + 1]))
441 {
442 ch = JS7_UNHEX(chars[i]) * 16 + JS7_UNHEX(chars[i + 1]);
443 i += 2;
444 } else if (i + 4 < length && chars[i] == 'u' &&
445 JS7_ISHEX(chars[i + 1]) && JS7_ISHEX(chars[i + 2]) &&
446 JS7_ISHEX(chars[i + 3]) && JS7_ISHEX(chars[i + 4]))
447 {
448 ch = (((((JS7_UNHEX(chars[i + 1]) << 4)
449 + JS7_UNHEX(chars[i + 2])) << 4)
450 + JS7_UNHEX(chars[i + 3])) << 4)
451 + JS7_UNHEX(chars[i + 4]);
452 i += 5;
453 }
454 }
455 newchars[ni++] = ch;
456 }
457 newchars[ni] = 0;
459 str = js_NewString(cx, newchars, ni, 0);
460 if (!str) {
461 JS_free(cx, newchars);
462 return JS_FALSE;
463 }
464 *rval = STRING_TO_JSVAL(str);
465 return JS_TRUE;
466 }
468 #if JS_HAS_UNEVAL
469 static JSBool
470 str_uneval(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
471 {
472 JSString *str;
474 str = js_ValueToSource(cx, argv[0]);
475 if (!str)
476 return JS_FALSE;
477 *rval = STRING_TO_JSVAL(str);
478 return JS_TRUE;
479 }
480 #endif
482 const char js_escape_str[] = "escape";
483 const char js_unescape_str[] = "unescape";
484 #if JS_HAS_UNEVAL
485 const char js_uneval_str[] = "uneval";
486 #endif
487 const char js_decodeURI_str[] = "decodeURI";
488 const char js_encodeURI_str[] = "encodeURI";
489 const char js_decodeURIComponent_str[] = "decodeURIComponent";
490 const char js_encodeURIComponent_str[] = "encodeURIComponent";
492 static JSFunctionSpec string_functions[] = {
493 {js_escape_str, js_str_escape, 1,0,0},
494 {js_unescape_str, str_unescape, 1,0,0},
495 #if JS_HAS_UNEVAL
496 {js_uneval_str, str_uneval, 1,0,0},
497 #endif
498 {js_decodeURI_str, str_decodeURI, 1,0,0},
499 {js_encodeURI_str, str_encodeURI, 1,0,0},
500 {js_decodeURIComponent_str, str_decodeURI_Component, 1,0,0},
501 {js_encodeURIComponent_str, str_encodeURI_Component, 1,0,0},
503 {0,0,0,0,0}
504 };
506 jschar js_empty_ucstr[] = {0};
507 JSSubString js_EmptySubString = {0, js_empty_ucstr};
509 enum string_tinyid {
510 STRING_LENGTH = -1
511 };
513 static JSPropertySpec string_props[] = {
514 {js_length_str, STRING_LENGTH,
515 JSPROP_READONLY|JSPROP_PERMANENT|JSPROP_SHARED, 0,0},
516 {0,0,0,0,0}
517 };
519 static JSBool
520 str_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
521 {
522 JSString *str;
523 jsint slot;
525 if (!JSVAL_IS_INT(id))
526 return JS_TRUE;
528 /*
529 * Call js_ValueToString because getters and setters can be invoked on
530 * objects of different class, unlike enumerate, resolve, and the other
531 * class hooks.
532 */
533 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
534 if (!str)
535 return JS_FALSE;
537 slot = JSVAL_TO_INT(id);
538 if (slot == STRING_LENGTH)
539 *vp = INT_TO_JSVAL((jsint) JSSTRING_LENGTH(str));
540 return JS_TRUE;
541 }
543 #define STRING_ELEMENT_ATTRS (JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_PERMANENT)
545 static JSBool
546 str_enumerate(JSContext *cx, JSObject *obj)
547 {
548 JSString *str, *str1;
549 size_t i, length;
551 /* Avoid infinite recursion via js_obj_toSource (see bug 271477). */
552 if (JS_VERSION_IS_1_2(cx))
553 return JS_TRUE;
555 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
556 if (!str)
557 return JS_TRUE;
558 cx->newborn[GCX_STRING] = (JSGCThing *) str;
560 length = JSSTRING_LENGTH(str);
561 for (i = 0; i < length; i++) {
562 str1 = js_NewDependentString(cx, str, i, 1, 0);
563 if (!str1)
564 return JS_FALSE;
565 if (!OBJ_DEFINE_PROPERTY(cx, obj, INT_TO_JSID(i),
566 STRING_TO_JSVAL(str1), NULL, NULL,
567 STRING_ELEMENT_ATTRS, NULL)) {
568 return JS_FALSE;
569 }
570 }
571 return JS_TRUE;
572 }
574 static JSBool
575 str_resolve(JSContext *cx, JSObject *obj, jsval id, uintN flags,
576 JSObject **objp)
577 {
578 JSString *str, *str1;
579 jsint slot;
581 if (!JSVAL_IS_INT(id) || (flags & JSRESOLVE_ASSIGNING))
582 return JS_TRUE;
584 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
585 if (!str)
586 return JS_TRUE;
587 cx->newborn[GCX_STRING] = (JSGCThing *) str;
589 slot = JSVAL_TO_INT(id);
590 if ((size_t)slot < JSSTRING_LENGTH(str)) {
591 str1 = js_NewDependentString(cx, str, (size_t)slot, 1, 0);
592 if (!str1)
593 return JS_FALSE;
594 if (!OBJ_DEFINE_PROPERTY(cx, obj, INT_TO_JSID(slot),
595 STRING_TO_JSVAL(str1), NULL, NULL,
596 STRING_ELEMENT_ATTRS, NULL)) {
597 return JS_FALSE;
598 }
599 *objp = obj;
600 }
601 return JS_TRUE;
602 }
604 JSClass js_StringClass = {
605 js_String_str,
606 JSCLASS_HAS_PRIVATE | JSCLASS_NEW_RESOLVE,
607 JS_PropertyStub, JS_PropertyStub, str_getProperty, JS_PropertyStub,
608 str_enumerate, (JSResolveOp)str_resolve, JS_ConvertStub, JS_FinalizeStub,
609 JSCLASS_NO_OPTIONAL_MEMBERS
610 };
612 #if JS_HAS_TOSOURCE
614 /*
615 * String.prototype.quote is generic (as are most string methods), unlike
616 * toSource, toString, and valueOf.
617 */
618 static JSBool
619 str_quote(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
620 {
621 JSString *str;
623 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
624 if (!str)
625 return JS_FALSE;
626 argv[-1] = STRING_TO_JSVAL(str);
628 str = js_QuoteString(cx, str, '"');
629 if (!str)
630 return JS_FALSE;
631 *rval = STRING_TO_JSVAL(str);
632 return JS_TRUE;
633 }
635 static JSBool
636 str_toSource(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
637 {
638 jsval v;
639 JSString *str;
640 size_t i, j, k, n;
641 char buf[16];
642 jschar *s, *t;
644 if (!JS_InstanceOf(cx, obj, &js_StringClass, argv))
645 return JS_FALSE;
646 v = OBJ_GET_SLOT(cx, obj, JSSLOT_PRIVATE);
647 if (!JSVAL_IS_STRING(v))
648 return js_obj_toSource(cx, obj, argc, argv, rval);
649 str = js_QuoteString(cx, JSVAL_TO_STRING(v), '"');
650 if (!str)
651 return JS_FALSE;
652 j = JS_snprintf(buf, sizeof buf, "(new %s(", js_StringClass.name);
653 s = JSSTRING_CHARS(str);
654 k = JSSTRING_LENGTH(str);
655 n = j + k + 2;
656 t = (jschar *) JS_malloc(cx, (n + 1) * sizeof(jschar));
657 if (!t)
658 return JS_FALSE;
659 for (i = 0; i < j; i++)
660 t[i] = buf[i];
661 for (j = 0; j < k; i++, j++)
662 t[i] = s[j];
663 t[i++] = ')';
664 t[i++] = ')';
665 t[i] = 0;
666 str = js_NewString(cx, t, n, 0);
667 if (!str) {
668 JS_free(cx, t);
669 return JS_FALSE;
670 }
671 *rval = STRING_TO_JSVAL(str);
672 return JS_TRUE;
673 }
675 #endif /* JS_HAS_TOSOURCE */
677 static JSBool
678 str_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
679 {
680 jsval v;
682 if (!JS_InstanceOf(cx, obj, &js_StringClass, argv))
683 return JS_FALSE;
684 v = OBJ_GET_SLOT(cx, obj, JSSLOT_PRIVATE);
685 if (!JSVAL_IS_STRING(v))
686 return js_obj_toString(cx, obj, argc, argv, rval);
687 *rval = v;
688 return JS_TRUE;
689 }
691 static JSBool
692 str_valueOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
693 {
694 if (!JS_InstanceOf(cx, obj, &js_StringClass, argv))
695 return JS_FALSE;
696 *rval = OBJ_GET_SLOT(cx, obj, JSSLOT_PRIVATE);
697 return JS_TRUE;
698 }
700 /*
701 * Java-like string native methods.
702 */
703 static JSBool
704 str_substring(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
705 jsval *rval)
706 {
707 JSString *str;
708 jsdouble d;
709 jsdouble length, begin, end;
711 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
712 if (!str)
713 return JS_FALSE;
714 argv[-1] = STRING_TO_JSVAL(str);
716 if (argc != 0) {
717 if (!js_ValueToNumber(cx, argv[0], &d))
718 return JS_FALSE;
719 length = JSSTRING_LENGTH(str);
720 begin = js_DoubleToInteger(d);
721 if (begin < 0)
722 begin = 0;
723 else if (begin > length)
724 begin = length;
726 if (argc == 1) {
727 end = length;
728 } else {
729 if (!js_ValueToNumber(cx, argv[1], &d))
730 return JS_FALSE;
731 end = js_DoubleToInteger(d);
732 if (end < 0)
733 end = 0;
734 else if (end > length)
735 end = length;
736 if (end < begin) {
737 if (!JS_VERSION_IS_1_2(cx)) {
738 /* XXX emulate old JDK1.0 java.lang.String.substring. */
739 jsdouble tmp = begin;
740 begin = end;
741 end = tmp;
742 } else {
743 end = begin;
744 }
745 }
746 }
748 str = js_NewDependentString(cx, str, (size_t)begin,
749 (size_t)(end - begin), 0);
750 if (!str)
751 return JS_FALSE;
752 }
753 *rval = STRING_TO_JSVAL(str);
754 return JS_TRUE;
755 }
757 static JSBool
758 str_toLowerCase(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
759 jsval *rval)
760 {
761 JSString *str;
762 size_t i, n;
763 jschar *s, *news;
765 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
766 if (!str)
767 return JS_FALSE;
768 argv[-1] = STRING_TO_JSVAL(str);
770 n = JSSTRING_LENGTH(str);
771 news = (jschar *) JS_malloc(cx, (n + 1) * sizeof(jschar));
772 if (!news)
773 return JS_FALSE;
774 s = JSSTRING_CHARS(str);
775 for (i = 0; i < n; i++)
776 news[i] = JS_TOLOWER(s[i]);
777 news[n] = 0;
778 str = js_NewString(cx, news, n, 0);
779 if (!str) {
780 JS_free(cx, news);
781 return JS_FALSE;
782 }
783 *rval = STRING_TO_JSVAL(str);
784 return JS_TRUE;
785 }
787 static JSBool
788 str_toLocaleLowerCase(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
789 jsval *rval)
790 {
791 JSString *str;
793 /*
794 * Forcefully ignore the first (or any) argument and return toLowerCase(),
795 * ECMA has reserved that argument, presumably for defining the locale.
796 */
797 if (cx->localeCallbacks && cx->localeCallbacks->localeToLowerCase) {
798 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
799 if (!str)
800 return JS_FALSE;
801 argv[-1] = STRING_TO_JSVAL(str);
802 return cx->localeCallbacks->localeToLowerCase(cx, str, rval);
803 }
804 return str_toLowerCase(cx, obj, 0, argv, rval);
805 }
807 static JSBool
808 str_toUpperCase(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
809 jsval *rval)
810 {
811 JSString *str;
812 size_t i, n;
813 jschar *s, *news;
815 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
816 if (!str)
817 return JS_FALSE;
818 argv[-1] = STRING_TO_JSVAL(str);
820 n = JSSTRING_LENGTH(str);
821 news = (jschar *) JS_malloc(cx, (n + 1) * sizeof(jschar));
822 if (!news)
823 return JS_FALSE;
824 s = JSSTRING_CHARS(str);
825 for (i = 0; i < n; i++)
826 news[i] = JS_TOUPPER(s[i]);
827 news[n] = 0;
828 str = js_NewString(cx, news, n, 0);
829 if (!str) {
830 JS_free(cx, news);
831 return JS_FALSE;
832 }
833 *rval = STRING_TO_JSVAL(str);
834 return JS_TRUE;
835 }
837 static JSBool
838 str_toLocaleUpperCase(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
839 jsval *rval)
840 {
841 JSString *str;
843 /*
844 * Forcefully ignore the first (or any) argument and return toUpperCase(),
845 * ECMA has reserved that argument, presumbaly for defining the locale.
846 */
847 if (cx->localeCallbacks && cx->localeCallbacks->localeToUpperCase) {
848 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
849 if (!str)
850 return JS_FALSE;
851 argv[-1] = STRING_TO_JSVAL(str);
852 return cx->localeCallbacks->localeToUpperCase(cx, str, rval);
853 }
854 return str_toUpperCase(cx, obj, 0, argv, rval);
855 }
857 static JSBool
858 str_localeCompare(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
859 jsval *rval)
860 {
861 JSString *str, *thatStr;
863 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
864 if (!str)
865 return JS_FALSE;
866 argv[-1] = STRING_TO_JSVAL(str);
868 if (argc == 0) {
869 *rval = JSVAL_ZERO;
870 } else {
871 thatStr = js_ValueToString(cx, argv[0]);
872 if (!thatStr)
873 return JS_FALSE;
874 if (cx->localeCallbacks && cx->localeCallbacks->localeCompare) {
875 argv[0] = STRING_TO_JSVAL(thatStr);
876 return cx->localeCallbacks->localeCompare(cx, str, thatStr, rval);
877 }
878 *rval = INT_TO_JSVAL(js_CompareStrings(str, thatStr));
879 }
880 return JS_TRUE;
881 }
883 static JSBool
884 str_charAt(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
885 {
886 JSString *str;
887 jsdouble d;
888 size_t index;
890 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
891 if (!str)
892 return JS_FALSE;
893 argv[-1] = STRING_TO_JSVAL(str);
895 if (argc == 0) {
896 d = 0.0;
897 } else {
898 if (!js_ValueToNumber(cx, argv[0], &d))
899 return JS_FALSE;
900 d = js_DoubleToInteger(d);
901 }
903 if (d < 0 || JSSTRING_LENGTH(str) <= d) {
904 *rval = JS_GetEmptyStringValue(cx);
905 } else {
906 index = (size_t)d;
907 str = js_NewDependentString(cx, str, index, 1, 0);
908 if (!str)
909 return JS_FALSE;
910 *rval = STRING_TO_JSVAL(str);
911 }
912 return JS_TRUE;
913 }
915 static JSBool
916 str_charCodeAt(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
917 jsval *rval)
918 {
919 JSString *str;
920 jsdouble d;
921 size_t index;
923 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
924 if (!str)
925 return JS_FALSE;
926 argv[-1] = STRING_TO_JSVAL(str);
928 if (argc == 0) {
929 d = 0.0;
930 } else {
931 if (!js_ValueToNumber(cx, argv[0], &d))
932 return JS_FALSE;
933 d = js_DoubleToInteger(d);
934 }
936 if (d < 0 || JSSTRING_LENGTH(str) <= d) {
937 *rval = JS_GetNaNValue(cx);
938 } else {
939 index = (size_t)d;
940 *rval = INT_TO_JSVAL((jsint) JSSTRING_CHARS(str)[index]);
941 }
942 return JS_TRUE;
943 }
945 jsint
946 js_BoyerMooreHorspool(const jschar *text, jsint textlen,
947 const jschar *pat, jsint patlen,
948 jsint start)
949 {
950 jsint i, j, k, m;
951 uint8 skip[BMH_CHARSET_SIZE];
952 jschar c;
954 JS_ASSERT(0 < patlen && patlen <= BMH_PATLEN_MAX);
955 for (i = 0; i < BMH_CHARSET_SIZE; i++)
956 skip[i] = (uint8)patlen;
957 m = patlen - 1;
958 for (i = 0; i < m; i++) {
959 c = pat[i];
960 if (c >= BMH_CHARSET_SIZE)
961 return BMH_BAD_PATTERN;
962 skip[c] = (uint8)(m - i);
963 }
964 for (k = start + m;
965 k < textlen;
966 k += ((c = text[k]) >= BMH_CHARSET_SIZE) ? patlen : skip[c]) {
967 for (i = k, j = m; ; i--, j--) {
968 if (j < 0)
969 return i + 1;
970 if (text[i] != pat[j])
971 break;
972 }
973 }
974 return -1;
975 }
977 static JSBool
978 str_indexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
979 {
980 JSString *str, *str2;
981 jsint i, j, index, textlen, patlen;
982 const jschar *text, *pat;
983 jsdouble d;
985 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
986 if (!str)
987 return JS_FALSE;
988 argv[-1] = STRING_TO_JSVAL(str);
989 text = JSSTRING_CHARS(str);
990 textlen = (jsint) JSSTRING_LENGTH(str);
992 str2 = js_ValueToString(cx, argv[0]);
993 if (!str2)
994 return JS_FALSE;
995 argv[0] = STRING_TO_JSVAL(str2);
996 pat = JSSTRING_CHARS(str2);
997 patlen = (jsint) JSSTRING_LENGTH(str2);
999 if (argc > 1) {
1000 if (!js_ValueToNumber(cx, argv[1], &d))
1001 return JS_FALSE;
1002 d = js_DoubleToInteger(d);
1003 if (d < 0)
1004 i = 0;
1005 else if (d > textlen)
1006 i = textlen;
1007 else
1008 i = (jsint)d;
1009 } else {
1010 i = 0;
1011 }
1012 if (patlen == 0) {
1013 *rval = INT_TO_JSVAL(i);
1014 return JS_TRUE;
1015 }
1017 /* XXX tune the BMH threshold (512) */
1018 if ((jsuint)(patlen - 2) <= BMH_PATLEN_MAX - 2 && textlen >= 512) {
1019 index = js_BoyerMooreHorspool(text, textlen, pat, patlen, i);
1020 if (index != BMH_BAD_PATTERN)
1021 goto out;
1022 }
1024 index = -1;
1025 j = 0;
1026 while (i + j < textlen) {
1027 if (text[i + j] == pat[j]) {
1028 if (++j == patlen) {
1029 index = i;
1030 break;
1031 }
1032 } else {
1033 i++;
1034 j = 0;
1035 }
1036 }
1038 out:
1039 *rval = INT_TO_JSVAL(index);
1040 return JS_TRUE;
1041 }
1043 static JSBool
1044 str_lastIndexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1045 jsval *rval)
1046 {
1047 JSString *str, *str2;
1048 const jschar *text, *pat;
1049 jsint i, j, textlen, patlen;
1050 jsdouble d;
1052 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
1053 if (!str)
1054 return JS_FALSE;
1055 argv[-1] = STRING_TO_JSVAL(str);
1056 text = JSSTRING_CHARS(str);
1057 textlen = (jsint) JSSTRING_LENGTH(str);
1059 str2 = js_ValueToString(cx, argv[0]);
1060 if (!str2)
1061 return JS_FALSE;
1062 argv[0] = STRING_TO_JSVAL(str2);
1063 pat = JSSTRING_CHARS(str2);
1064 patlen = (jsint) JSSTRING_LENGTH(str2);
1066 if (argc > 1) {
1067 if (!js_ValueToNumber(cx, argv[1], &d))
1068 return JS_FALSE;
1069 if (JSDOUBLE_IS_NaN(d)) {
1070 i = textlen;
1071 } else {
1072 d = js_DoubleToInteger(d);
1073 if (d < 0)
1074 i = 0;
1075 else if (d > textlen)
1076 i = textlen;
1077 else
1078 i = (jsint)d;
1079 }
1080 } else {
1081 i = textlen;
1082 }
1084 if (patlen == 0) {
1085 *rval = INT_TO_JSVAL(i);
1086 return JS_TRUE;
1087 }
1089 j = 0;
1090 while (i >= 0) {
1091 /* Don't assume that text is NUL-terminated: it could be dependent. */
1092 if (i + j < textlen && text[i + j] == pat[j]) {
1093 if (++j == patlen)
1094 break;
1095 } else {
1096 i--;
1097 j = 0;
1098 }
1099 }
1100 *rval = INT_TO_JSVAL(i);
1101 return JS_TRUE;
1102 }
1104 /*
1105 * Perl-inspired string functions.
1106 */
1107 #if JS_HAS_REGEXPS
1108 typedef struct GlobData {
1109 uintN flags; /* inout: mode and flag bits, see below */
1110 uintN optarg; /* in: index of optional flags argument */
1111 JSString *str; /* out: 'this' parameter object as string */
1112 JSRegExp *regexp; /* out: regexp parameter object private data */
1113 } GlobData;
1115 /*
1116 * Mode and flag bit definitions for match_or_replace's GlobData.flags field.
1117 */
1118 #define MODE_MATCH 0x00 /* in: return match array on success */
1119 #define MODE_REPLACE 0x01 /* in: match and replace */
1120 #define MODE_SEARCH 0x02 /* in: search only, return match index or -1 */
1121 #define GET_MODE(f) ((f) & 0x03)
1122 #define FORCE_FLAT 0x04 /* in: force flat (non-regexp) string match */
1123 #define KEEP_REGEXP 0x08 /* inout: keep GlobData.regexp alive for caller
1124 of match_or_replace; if set on input
1125 but clear on output, regexp ownership
1126 does not pass to caller */
1127 #define GLOBAL_REGEXP 0x10 /* out: regexp had the 'g' flag */
1129 static JSBool
1130 match_or_replace(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1131 JSBool (*glob)(JSContext *cx, jsint count, GlobData *data),
1132 GlobData *data, jsval *rval)
1133 {
1134 JSString *str, *src, *opt;
1135 JSObject *reobj;
1136 JSRegExp *re;
1137 size_t index, length;
1138 JSBool ok, test;
1139 jsint count;
1141 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
1142 if (!str)
1143 return JS_FALSE;
1144 argv[-1] = STRING_TO_JSVAL(str);
1145 data->str = str;
1147 if (JSVAL_IS_REGEXP(cx, argv[0])) {
1148 reobj = JSVAL_TO_OBJECT(argv[0]);
1149 re = (JSRegExp *) JS_GetPrivate(cx, reobj);
1150 } else {
1151 src = js_ValueToString(cx, argv[0]);
1152 if (!src)
1153 return JS_FALSE;
1154 if (data->optarg < argc) {
1155 argv[0] = STRING_TO_JSVAL(src);
1156 opt = js_ValueToString(cx, argv[data->optarg]);
1157 if (!opt)
1158 return JS_FALSE;
1159 } else {
1160 opt = NULL;
1161 }
1162 re = js_NewRegExpOpt(cx, NULL, src, opt,
1163 (data->flags & FORCE_FLAT) != 0);
1164 if (!re)
1165 return JS_FALSE;
1166 reobj = NULL;
1167 }
1168 /* From here on, all control flow must reach the matching DROP. */
1169 data->regexp = re;
1170 HOLD_REGEXP(cx, re);
1172 if (re->flags & JSREG_GLOB)
1173 data->flags |= GLOBAL_REGEXP;
1174 index = 0;
1175 if (GET_MODE(data->flags) == MODE_SEARCH) {
1176 ok = js_ExecuteRegExp(cx, re, str, &index, JS_TRUE, rval);
1177 if (ok) {
1178 *rval = (*rval == JSVAL_TRUE)
1179 ? INT_TO_JSVAL(cx->regExpStatics.leftContext.length)
1180 : INT_TO_JSVAL(-1);
1181 }
1182 } else if (data->flags & GLOBAL_REGEXP) {
1183 if (reobj) {
1184 /* Set the lastIndex property's reserved slot to 0. */
1185 ok = js_SetLastIndex(cx, reobj, 0);
1186 } else {
1187 ok = JS_TRUE;
1188 }
1189 if (ok) {
1190 length = JSSTRING_LENGTH(str);
1191 for (count = 0; index <= length; count++) {
1192 ok = js_ExecuteRegExp(cx, re, str, &index, JS_TRUE, rval);
1193 if (!ok || *rval != JSVAL_TRUE)
1194 break;
1195 ok = glob(cx, count, data);
1196 if (!ok)
1197 break;
1198 if (cx->regExpStatics.lastMatch.length == 0) {
1199 if (index == length)
1200 break;
1201 index++;
1202 }
1203 }
1204 }
1205 } else {
1206 if (GET_MODE(data->flags) == MODE_REPLACE) {
1207 test = JS_TRUE;
1208 } else {
1209 /*
1210 * MODE_MATCH implies str_match is being called from a script or a
1211 * scripted function. If the caller cares only about testing null
1212 * vs. non-null return value, optimize away the array object that
1213 * would normally be returned in *rval.
1214 */
1215 JSStackFrame *fp = cx->fp->down;
1217 /* Skip Function.prototype.call and .apply frames. */
1218 while (fp && !fp->pc) {
1219 JS_ASSERT(!fp->script);
1220 fp = fp->down;
1221 }
1223 /* Assume a full array result is required, then prove otherwise. */
1224 test = JS_FALSE;
1225 if (fp) {
1226 JS_ASSERT(*fp->pc == JSOP_CALL || *fp->pc == JSOP_NEW);
1227 JS_ASSERT(js_CodeSpec[*fp->pc].length == 3);
1228 switch (fp->pc[3]) {
1229 case JSOP_POP:
1230 case JSOP_IFEQ:
1231 case JSOP_IFNE:
1232 case JSOP_IFEQX:
1233 case JSOP_IFNEX:
1234 test = JS_TRUE;
1235 break;
1236 default:;
1237 }
1238 }
1239 }
1240 ok = js_ExecuteRegExp(cx, re, str, &index, test, rval);
1241 }
1243 DROP_REGEXP(cx, re);
1244 if (reobj) {
1245 /* Tell our caller that it doesn't need to destroy data->regexp. */
1246 data->flags &= ~KEEP_REGEXP;
1247 } else if (!(data->flags & KEEP_REGEXP)) {
1248 /* Caller didn't want to keep data->regexp, so null and destroy it. */
1249 data->regexp = NULL;
1250 js_DestroyRegExp(cx, re);
1251 }
1253 return ok;
1254 }
1256 typedef struct MatchData {
1257 GlobData base;
1258 jsval *arrayval; /* NB: local root pointer */
1259 } MatchData;
1261 static JSBool
1262 match_glob(JSContext *cx, jsint count, GlobData *data)
1263 {
1264 MatchData *mdata;
1265 JSObject *arrayobj;
1266 JSSubString *matchsub;
1267 JSString *matchstr;
1268 jsval v;
1270 mdata = (MatchData *)data;
1271 arrayobj = JSVAL_TO_OBJECT(*mdata->arrayval);
1272 if (!arrayobj) {
1273 arrayobj = js_ConstructObject(cx, &js_ArrayClass, NULL, NULL, 0, NULL);
1274 if (!arrayobj)
1275 return JS_FALSE;
1276 *mdata->arrayval = OBJECT_TO_JSVAL(arrayobj);
1277 }
1278 matchsub = &cx->regExpStatics.lastMatch;
1279 matchstr = js_NewStringCopyN(cx, matchsub->chars, matchsub->length, 0);
1280 if (!matchstr)
1281 return JS_FALSE;
1282 v = STRING_TO_JSVAL(matchstr);
1283 return js_SetProperty(cx, arrayobj, INT_TO_JSID(count), &v);
1284 }
1286 static JSBool
1287 str_match(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1288 {
1289 MatchData mdata;
1290 JSBool ok;
1292 mdata.base.flags = MODE_MATCH;
1293 mdata.base.optarg = 1;
1294 mdata.arrayval = &argv[2];
1295 *mdata.arrayval = JSVAL_NULL;
1296 ok = match_or_replace(cx, obj, argc, argv, match_glob, &mdata.base, rval);
1297 if (ok && !JSVAL_IS_NULL(*mdata.arrayval))
1298 *rval = *mdata.arrayval;
1299 return ok;
1300 }
1302 static JSBool
1303 str_search(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1304 {
1305 GlobData data;
1307 data.flags = MODE_SEARCH;
1308 data.optarg = 1;
1309 return match_or_replace(cx, obj, argc, argv, NULL, &data, rval);
1310 }
1312 typedef struct ReplaceData {
1313 GlobData base; /* base struct state */
1314 JSObject *lambda; /* replacement function object or null */
1315 JSString *repstr; /* replacement string */
1316 jschar *dollar; /* null or pointer to first $ in repstr */
1317 jschar *dollarEnd; /* limit pointer for js_strchr_limit */
1318 jschar *chars; /* result chars, null initially */
1319 size_t length; /* result length, 0 initially */
1320 jsint index; /* index in result of next replacement */
1321 jsint leftIndex; /* left context index in base.str->chars */
1322 JSSubString dollarStr; /* for "$$" interpret_dollar result */
1323 } ReplaceData;
1325 static JSSubString *
1326 interpret_dollar(JSContext *cx, jschar *dp, jschar *ep, ReplaceData *rdata,
1327 size_t *skip)
1328 {
1329 JSVersion version;
1330 JSRegExpStatics *res;
1331 jschar dc, *cp;
1332 uintN num, tmp;
1333 JSString *str;
1335 JS_ASSERT(*dp == '$');
1337 /*
1338 * Allow a real backslash (literal "\\" before "$1") to escape "$1", e.g.
1339 * Do this only for versions strictly less than ECMAv3.
1340 */
1341 version = cx->version & JSVERSION_MASK;
1342 if (version != JSVERSION_DEFAULT && version <= JSVERSION_1_4) {
1343 if (dp > JSSTRING_CHARS(rdata->repstr) && dp[-1] == '\\')
1344 return NULL;
1345 }
1347 /* If there is only a dollar, bail now */
1348 if (dp + 1 >= ep)
1349 return NULL;
1351 /* Interpret all Perl match-induced dollar variables. */
1352 res = &cx->regExpStatics;
1353 dc = dp[1];
1354 if (JS7_ISDEC(dc)) {
1355 if (version != JSVERSION_DEFAULT && version <= JSVERSION_1_4) {
1356 if (dc == '0')
1357 return NULL;
1359 /* Check for overflow to avoid gobbling arbitrary decimal digits. */
1360 num = 0;
1361 cp = dp;
1362 while (++cp < ep && (dc = *cp, JS7_ISDEC(dc))) {
1363 tmp = 10 * num + JS7_UNDEC(dc);
1364 if (tmp < num)
1365 break;
1366 num = tmp;
1367 }
1368 } else { /* ECMA 3, 1-9 or 01-99 */
1369 num = JS7_UNDEC(dc);
1370 if (num > res->parenCount)
1371 return NULL;
1373 cp = dp + 2;
1374 if (cp < ep && (dc = *cp, JS7_ISDEC(dc))) {
1375 tmp = 10 * num + JS7_UNDEC(dc);
1376 if (tmp <= res->parenCount) {
1377 cp++;
1378 num = tmp;
1379 }
1380 }
1381 if (num == 0)
1382 return NULL;
1383 }
1384 /* Adjust num from 1 $n-origin to 0 array-index-origin. */
1385 num--;
1386 *skip = cp - dp;
1387 return REGEXP_PAREN_SUBSTRING(res, num);
1388 }
1390 *skip = 2;
1391 switch (dc) {
1392 case '$':
1393 rdata->dollarStr.chars = dp;
1394 rdata->dollarStr.length = 1;
1395 return &rdata->dollarStr;
1396 case '&':
1397 return &res->lastMatch;
1398 case '+':
1399 return &res->lastParen;
1400 case '`':
1401 if (version == JSVERSION_1_2) {
1402 /*
1403 * JS1.2 imitated the Perl4 bug where left context at each step
1404 * in an iterative use of a global regexp started from last match,
1405 * not from the start of the target string. But Perl4 does start
1406 * $` at the beginning of the target string when it is used in a
1407 * substitution, so we emulate that special case here.
1408 */
1409 str = rdata->base.str;
1410 res->leftContext.chars = JSSTRING_CHARS(str);
1411 res->leftContext.length = res->lastMatch.chars
1412 - JSSTRING_CHARS(str);
1413 }
1414 return &res->leftContext;
1415 case '\'':
1416 return &res->rightContext;
1417 }
1418 return NULL;
1419 }
1421 static JSBool
1422 find_replen(JSContext *cx, ReplaceData *rdata, size_t *sizep)
1423 {
1424 JSString *repstr;
1425 size_t replen, skip;
1426 jschar *dp, *ep;
1427 JSSubString *sub;
1428 #if JS_HAS_REPLACE_LAMBDA
1429 JSObject *lambda;
1431 lambda = rdata->lambda;
1432 if (lambda) {
1433 uintN argc, i, j, m, n, p;
1434 jsval *sp, *oldsp, rval;
1435 void *mark;
1436 JSStackFrame *fp;
1437 JSBool ok;
1439 /*
1440 * Save the regExpStatics from the current regexp, since they may be
1441 * clobbered by a RegExp usage in the lambda function. Note that all
1442 * members of JSRegExpStatics are JSSubStrings, so not GC roots, save
1443 * input, which is rooted otherwise via argv[-1] in str_replace.
1444 */
1445 JSRegExpStatics save = cx->regExpStatics;
1446 JSBool freeMoreParens = JS_FALSE;
1448 /*
1449 * In the lambda case, not only do we find the replacement string's
1450 * length, we compute repstr and return it via rdata for use within
1451 * do_replace. The lambda is called with arguments ($&, $1, $2, ...,
1452 * index, input), i.e., all the properties of a regexp match array.
1453 * For $&, etc., we must create string jsvals from cx->regExpStatics.
1454 * We grab up stack space to keep the newborn strings GC-rooted.
1455 */
1456 p = rdata->base.regexp->parenCount;
1457 argc = 1 + p + 2;
1458 sp = js_AllocStack(cx, 2 + argc, &mark);
1459 if (!sp)
1460 return JS_FALSE;
1462 /* Push lambda and its 'this' parameter. */
1463 *sp++ = OBJECT_TO_JSVAL(lambda);
1464 *sp++ = OBJECT_TO_JSVAL(OBJ_GET_PARENT(cx, lambda));
1466 #define PUSH_REGEXP_STATIC(sub) \
1467 JS_BEGIN_MACRO \
1468 JSString *str = js_NewStringCopyN(cx, \
1469 cx->regExpStatics.sub.chars, \
1470 cx->regExpStatics.sub.length, \
1471 0); \
1472 if (!str) { \
1473 ok = JS_FALSE; \
1474 goto lambda_out; \
1475 } \
1476 *sp++ = STRING_TO_JSVAL(str); \
1477 JS_END_MACRO
1479 /* Push $&, $1, $2, ... */
1480 PUSH_REGEXP_STATIC(lastMatch);
1481 i = 0;
1482 m = cx->regExpStatics.parenCount;
1483 n = JS_MIN(m, 9);
1484 for (j = 0; i < n; i++, j++)
1485 PUSH_REGEXP_STATIC(parens[j]);
1486 for (j = 0; i < m; i++, j++)
1487 PUSH_REGEXP_STATIC(moreParens[j]);
1489 /*
1490 * We need to clear moreParens in the top-of-stack cx->regExpStatics
1491 * to it won't be possibly realloc'ed, leaving the bottom-of-stack
1492 * moreParens pointing to freed memory.
1493 */
1494 cx->regExpStatics.moreParens = NULL;
1495 freeMoreParens = JS_TRUE;
1497 #undef PUSH_REGEXP_STATIC
1499 /* Make sure to push undefined for any unmatched parens. */
1500 for (; i < p; i++)
1501 *sp++ = JSVAL_VOID;
1503 /* Push match index and input string. */
1504 *sp++ = INT_TO_JSVAL((jsint)cx->regExpStatics.leftContext.length);
1505 *sp++ = STRING_TO_JSVAL(rdata->base.str);
1507 /* Lift current frame to include the args and do the call. */
1508 fp = cx->fp;
1509 oldsp = fp->sp;
1510 fp->sp = sp;
1511 ok = js_Invoke(cx, argc, JSINVOKE_INTERNAL);
1512 rval = fp->sp[-1];
1513 fp->sp = oldsp;
1515 if (ok) {
1516 /*
1517 * NB: we count on the newborn string root to hold any string
1518 * created by this js_ValueToString that would otherwise be GC-
1519 * able, until we use rdata->repstr in do_replace.
1520 */
1521 repstr = js_ValueToString(cx, rval);
1522 if (!repstr) {
1523 ok = JS_FALSE;
1524 } else {
1525 rdata->repstr = repstr;
1526 *sizep = JSSTRING_LENGTH(repstr);
1527 }
1528 }
1530 lambda_out:
1531 js_FreeStack(cx, mark);
1532 if (freeMoreParens)
1533 JS_free(cx, cx->regExpStatics.moreParens);
1534 cx->regExpStatics = save;
1535 return ok;
1536 }
1537 #endif /* JS_HAS_REPLACE_LAMBDA */
1539 repstr = rdata->repstr;
1540 replen = JSSTRING_LENGTH(repstr);
1541 for (dp = rdata->dollar, ep = rdata->dollarEnd; dp;
1542 dp = js_strchr_limit(dp, '$', ep)) {
1543 sub = interpret_dollar(cx, dp, ep, rdata, &skip);
1544 if (sub) {
1545 replen += sub->length - skip;
1546 dp += skip;
1547 }
1548 else
1549 dp++;
1550 }
1551 *sizep = replen;
1552 return JS_TRUE;
1553 }
1555 static void
1556 do_replace(JSContext *cx, ReplaceData *rdata, jschar *chars)
1557 {
1558 JSString *repstr;
1559 jschar *bp, *cp, *dp, *ep;
1560 size_t len, skip;
1561 JSSubString *sub;
1563 repstr = rdata->repstr;
1564 bp = cp = JSSTRING_CHARS(repstr);
1565 for (dp = rdata->dollar, ep = rdata->dollarEnd; dp;
1566 dp = js_strchr_limit(dp, '$', ep)) {
1567 len = dp - cp;
1568 js_strncpy(chars, cp, len);
1569 chars += len;
1570 cp = dp;
1571 sub = interpret_dollar(cx, dp, ep, rdata, &skip);
1572 if (sub) {
1573 len = sub->length;
1574 js_strncpy(chars, sub->chars, len);
1575 chars += len;
1576 cp += skip;
1577 dp += skip;
1578 } else {
1579 dp++;
1580 }
1581 }
1582 js_strncpy(chars, cp, JSSTRING_LENGTH(repstr) - (cp - bp));
1583 }
1585 static JSBool
1586 replace_glob(JSContext *cx, jsint count, GlobData *data)
1587 {
1588 ReplaceData *rdata;
1589 JSString *str;
1590 size_t leftoff, leftlen, replen, growth;
1591 const jschar *left;
1592 jschar *chars;
1594 rdata = (ReplaceData *)data;
1595 str = data->str;
1596 leftoff = rdata->leftIndex;
1597 left = JSSTRING_CHARS(str) + leftoff;
1598 leftlen = cx->regExpStatics.lastMatch.chars - left;
1599 rdata->leftIndex = cx->regExpStatics.lastMatch.chars - JSSTRING_CHARS(str);
1600 rdata->leftIndex += cx->regExpStatics.lastMatch.length;
1601 if (!find_replen(cx, rdata, &replen))
1602 return JS_FALSE;
1603 growth = leftlen + replen;
1604 chars = (jschar *)
1605 (rdata->chars
1606 ? JS_realloc(cx, rdata->chars, (rdata->length + growth + 1)
1607 * sizeof(jschar))
1608 : JS_malloc(cx, (growth + 1) * sizeof(jschar)));
1609 if (!chars) {
1610 JS_free(cx, rdata->chars);
1611 rdata->chars = NULL;
1612 return JS_FALSE;
1613 }
1614 rdata->chars = chars;
1615 rdata->length += growth;
1616 chars += rdata->index;
1617 rdata->index += growth;
1618 js_strncpy(chars, left, leftlen);
1619 chars += leftlen;
1620 do_replace(cx, rdata, chars);
1621 return JS_TRUE;
1622 }
1624 static JSBool
1625 str_replace(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1626 {
1627 JSObject *lambda;
1628 JSString *repstr, *str;
1629 ReplaceData rdata;
1630 JSVersion version;
1631 JSBool ok;
1632 jschar *chars;
1633 size_t leftlen, rightlen, length;
1635 #if JS_HAS_REPLACE_LAMBDA
1636 if (JS_TypeOfValue(cx, argv[1]) == JSTYPE_FUNCTION) {
1637 lambda = JSVAL_TO_OBJECT(argv[1]);
1638 repstr = NULL;
1639 } else
1640 #endif
1641 {
1642 if (!JS_ConvertValue(cx, argv[1], JSTYPE_STRING, &argv[1]))
1643 return JS_FALSE;
1644 repstr = JSVAL_TO_STRING(argv[1]);
1645 lambda = NULL;
1646 }
1648 /*
1649 * For ECMA Edition 3, the first argument is to be converted to a string
1650 * to match in a "flat" sense (without regular expression metachars having
1651 * special meanings) UNLESS the first arg is a RegExp object.
1652 */
1653 rdata.base.flags = MODE_REPLACE | KEEP_REGEXP;
1654 version = cx->version & JSVERSION_MASK;
1655 if (version == JSVERSION_DEFAULT || version > JSVERSION_1_4)
1656 rdata.base.flags |= FORCE_FLAT;
1657 rdata.base.optarg = 2;
1659 rdata.lambda = lambda;
1660 rdata.repstr = repstr;
1661 if (repstr) {
1662 rdata.dollarEnd = JSSTRING_CHARS(repstr) + JSSTRING_LENGTH(repstr);
1663 rdata.dollar = js_strchr_limit(JSSTRING_CHARS(repstr), '$',
1664 rdata.dollarEnd);
1665 } else {
1666 rdata.dollar = rdata.dollarEnd = NULL;
1667 }
1668 rdata.chars = NULL;
1669 rdata.length = 0;
1670 rdata.index = 0;
1671 rdata.leftIndex = 0;
1673 ok = match_or_replace(cx, obj, argc, argv, replace_glob, &rdata.base, rval);
1674 if (!ok)
1675 return JS_FALSE;
1677 if (!rdata.chars) {
1678 if ((rdata.base.flags & GLOBAL_REGEXP) || *rval != JSVAL_TRUE) {
1679 /* Didn't match even once. */
1680 *rval = STRING_TO_JSVAL(rdata.base.str);
1681 goto out;
1682 }
1683 leftlen = cx->regExpStatics.leftContext.length;
1684 ok = find_replen(cx, &rdata, &length);
1685 if (!ok)
1686 goto out;
1687 length += leftlen;
1688 chars = (jschar *) JS_malloc(cx, (length + 1) * sizeof(jschar));
1689 if (!chars) {
1690 ok = JS_FALSE;
1691 goto out;
1692 }
1693 js_strncpy(chars, cx->regExpStatics.leftContext.chars, leftlen);
1694 do_replace(cx, &rdata, chars + leftlen);
1695 rdata.chars = chars;
1696 rdata.length = length;
1697 }
1699 rightlen = cx->regExpStatics.rightContext.length;
1700 length = rdata.length + rightlen;
1701 chars = (jschar *)
1702 JS_realloc(cx, rdata.chars, (length + 1) * sizeof(jschar));
1703 if (!chars) {
1704 JS_free(cx, rdata.chars);
1705 ok = JS_FALSE;
1706 goto out;
1707 }
1708 js_strncpy(chars + rdata.length, cx->regExpStatics.rightContext.chars,
1709 rightlen);
1710 chars[length] = 0;
1712 str = js_NewString(cx, chars, length, 0);
1713 if (!str) {
1714 JS_free(cx, chars);
1715 ok = JS_FALSE;
1716 goto out;
1717 }
1718 *rval = STRING_TO_JSVAL(str);
1720 out:
1721 /* If KEEP_REGEXP is still set, it's our job to destroy regexp now. */
1722 if (rdata.base.flags & KEEP_REGEXP)
1723 js_DestroyRegExp(cx, rdata.base.regexp);
1724 return ok;
1725 }
1726 #endif /* JS_HAS_REGEXPS */
1728 /*
1729 * Subroutine used by str_split to find the next split point in str, starting
1730 * at offset *ip and looking either for the separator substring given by sep,
1731 * or for the next re match. In the re case, return the matched separator in
1732 * *sep, and the possibly updated offset in *ip.
1733 *
1734 * Return -2 on error, -1 on end of string, >= 0 for a valid index of the next
1735 * separator occurrence if found, or str->length if no separator is found.
1736 */
1737 static jsint
1738 find_split(JSContext *cx, JSString *str, JSRegExp *re, jsint *ip,
1739 JSSubString *sep)
1740 {
1741 jsint i, j, k;
1742 jschar *chars;
1743 size_t length;
1745 /*
1746 * Stop if past end of string. If at end of string, we will compare the
1747 * null char stored there (by js_NewString*) to sep->chars[j] in the while
1748 * loop at the end of this function, so that
1749 *
1750 * "ab,".split(',') => ["ab", ""]
1751 *
1752 * and the resulting array converts back to the string "ab," for symmetry.
1753 * However, we ape Perl and do this only if there is a sufficiently large
1754 * limit argument (see str_split).
1755 */
1756 i = *ip;
1757 if ((size_t)i > JSSTRING_LENGTH(str))
1758 return -1;
1760 /*
1761 * Perl4 special case for str.split(' '), only if the user has selected
1762 * JavaScript1.2 explicitly. Split on whitespace, and skip leading w/s.
1763 * Strange but true, apparently modeled after awk.
1764 *
1765 * NB: we set sep->length to the length of the w/s run, so we must test
1766 * sep->chars[1] == 0 to make sure sep is just one space.
1767 */
1768 chars = JSSTRING_CHARS(str);
1769 length = JSSTRING_LENGTH(str);
1770 if (JS_VERSION_IS_1_2(cx) &&
1771 !re && *sep->chars == ' ' && sep->chars[1] == 0) {
1773 /* Skip leading whitespace if at front of str. */
1774 if (i == 0) {
1775 while (JS_ISSPACE(chars[i]))
1776 i++;
1777 *ip = i;
1778 }
1780 /* Don't delimit whitespace at end of string. */
1781 if ((size_t)i == length)
1782 return -1;
1784 /* Skip over the non-whitespace chars. */
1785 while ((size_t)i < length && !JS_ISSPACE(chars[i]))
1786 i++;
1788 /* Now skip the next run of whitespace. */
1789 j = i;
1790 while ((size_t)j < length && JS_ISSPACE(chars[j]))
1791 j++;
1793 /* Update sep->length to count delimiter chars. */
1794 sep->length = (size_t)(j - i);
1795 return i;
1796 }
1798 #if JS_HAS_REGEXPS
1799 /*
1800 * Match a regular expression against the separator at or above index i.
1801 * Call js_ExecuteRegExp with true for the test argument. On successful
1802 * match, get the separator from cx->regExpStatics.lastMatch.
1803 */
1804 if (re) {
1805 size_t index;
1806 jsval rval;
1808 again:
1809 /* JS1.2 deviated from Perl by never matching at end of string. */
1810 index = (size_t)i;
1811 if (!js_ExecuteRegExp(cx, re, str, &index, JS_TRUE, &rval))
1812 return -2;
1813 if (rval != JSVAL_TRUE) {
1814 /* Mismatch: ensure our caller advances i past end of string. */
1815 sep->length = 1;
1816 return length;
1817 }
1818 i = (jsint)index;
1819 *sep = cx->regExpStatics.lastMatch;
1820 if (sep->length == 0) {
1821 /*
1822 * Empty string match: never split on an empty match at the start
1823 * of a find_split cycle. Same rule as for an empty global match
1824 * in match_or_replace.
1825 */
1826 if (i == *ip) {
1827 /*
1828 * "Bump-along" to avoid sticking at an empty match, but don't
1829 * bump past end of string -- our caller must do that by adding
1830 * sep->length to our return value.
1831 */
1832 if ((size_t)i == length) {
1833 if (JS_VERSION_IS_1_2(cx)) {
1834 sep->length = 1;
1835 return i;
1836 }
1837 return -1;
1838 }
1839 i++;
1840 goto again;
1841 }
1842 if ((size_t)i == length) {
1843 /*
1844 * If there was a trivial zero-length match at the end of the
1845 * split, then we shouldn't output the matched string at the end
1846 * of the split array. See ECMA-262 Ed. 3, 15.5.4.14, Step 15.
1847 */
1848 sep->chars = NULL;
1849 }
1850 }
1851 JS_ASSERT((size_t)i >= sep->length);
1852 return i - sep->length;
1853 }
1854 #endif /* JS_HAS_REGEXPS */
1856 /*
1857 * Deviate from ECMA by never splitting an empty string by any separator
1858 * string into a non-empty array (an array of length 1 that contains the
1859 * empty string).
1860 */
1861 if (!JS_VERSION_IS_ECMA(cx) && length == 0)
1862 return -1;
1864 /*
1865 * Special case: if sep is the empty string, split str into one character
1866 * substrings. Let our caller worry about whether to split once at end of
1867 * string into an empty substring.
1868 *
1869 * For 1.2 compatibility, at the end of the string, we return the length as
1870 * the result, and set the separator length to 1 -- this allows the caller
1871 * to include an additional null string at the end of the substring list.
1872 */
1873 if (sep->length == 0) {
1874 if (JS_VERSION_IS_1_2(cx)) {
1875 if ((size_t)i == length) {
1876 sep->length = 1;
1877 return i;
1878 }
1879 return i + 1;
1880 }
1881 return ((size_t)i == length) ? -1 : i + 1;
1882 }
1884 /*
1885 * Now that we know sep is non-empty, search starting at i in str for an
1886 * occurrence of all of sep's chars. If we find them, return the index of
1887 * the first separator char. Otherwise, return length.
1888 */
1889 j = 0;
1890 while ((size_t)(k = i + j) < length) {
1891 if (chars[k] == sep->chars[j]) {
1892 if ((size_t)++j == sep->length)
1893 return i;
1894 } else {
1895 i++;
1896 j = 0;
1897 }
1898 }
1899 return k;
1900 }
1902 static JSBool
1903 str_split(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1904 {
1905 JSString *str, *sub;
1906 JSObject *arrayobj;
1907 jsval v;
1908 JSBool ok, limited;
1909 JSRegExp *re;
1910 JSSubString *sep, tmp;
1911 jsdouble d;
1912 jsint i, j;
1913 uint32 len, limit;
1915 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
1916 if (!str)
1917 return JS_FALSE;
1918 argv[-1] = STRING_TO_JSVAL(str);
1920 arrayobj = js_ConstructObject(cx, &js_ArrayClass, NULL, NULL, 0, NULL);
1921 if (!arrayobj)
1922 return JS_FALSE;
1923 *rval = OBJECT_TO_JSVAL(arrayobj);
1925 if (argc == 0) {
1926 v = STRING_TO_JSVAL(str);
1927 ok = JS_SetElement(cx, arrayobj, 0, &v);
1928 } else {
1929 #if JS_HAS_REGEXPS
1930 if (JSVAL_IS_REGEXP(cx, argv[0])) {
1931 re = (JSRegExp *) JS_GetPrivate(cx, JSVAL_TO_OBJECT(argv[0]));
1932 sep = &tmp;
1934 /* Set a magic value so we can detect a successful re match. */
1935 sep->chars = NULL;
1936 } else
1937 #endif
1938 {
1939 JSString *str2 = js_ValueToString(cx, argv[0]);
1940 if (!str2)
1941 return JS_FALSE;
1942 argv[0] = STRING_TO_JSVAL(str2);
1944 /*
1945 * Point sep at a local copy of str2's header because find_split
1946 * will modify sep->length.
1947 */
1948 tmp.length = JSSTRING_LENGTH(str2);
1949 tmp.chars = JSSTRING_CHARS(str2);
1950 sep = &tmp;
1951 re = NULL;
1952 }
1954 /* Use the second argument as the split limit, if given. */
1955 limited = (argc > 1) && !JSVAL_IS_VOID(argv[1]);
1956 limit = 0; /* Avoid warning. */
1957 if (limited) {
1958 if (!js_ValueToNumber(cx, argv[1], &d))
1959 return JS_FALSE;
1961 /* Clamp limit between 0 and 1 + string length. */
1962 if (!js_DoubleToECMAUint32(cx, d, &limit))
1963 return JS_FALSE;
1964 if (limit > JSSTRING_LENGTH(str))
1965 limit = 1 + JSSTRING_LENGTH(str);
1966 }
1968 len = i = 0;
1969 while ((j = find_split(cx, str, re, &i, sep)) >= 0) {
1970 if (limited && len >= limit)
1971 break;
1972 sub = js_NewDependentString(cx, str, i, (size_t)(j - i), 0);
1973 if (!sub)
1974 return JS_FALSE;
1975 v = STRING_TO_JSVAL(sub);
1976 if (!JS_SetElement(cx, arrayobj, len, &v))
1977 return JS_FALSE;
1978 len++;
1979 #if JS_HAS_REGEXPS
1980 /*
1981 * Imitate perl's feature of including parenthesized substrings
1982 * that matched part of the delimiter in the new array, after the
1983 * split substring that was delimited.
1984 */
1985 if (re && sep->chars) {
1986 uintN num;
1987 JSSubString *parsub;
1989 for (num = 0; num < cx->regExpStatics.parenCount; num++) {
1990 if (limited && len >= limit)
1991 break;
1992 parsub = REGEXP_PAREN_SUBSTRING(&cx->regExpStatics, num);
1993 sub = js_NewStringCopyN(cx, parsub->chars, parsub->length,
1994 0);
1995 if (!sub)
1996 return JS_FALSE;
1997 v = STRING_TO_JSVAL(sub);
1998 if (!JS_SetElement(cx, arrayobj, len, &v))
1999 return JS_FALSE;
2000 len++;
2001 }
2002 sep->chars = NULL;
2003 }
2004 #endif
2005 i = j + sep->length;
2006 if (!JS_VERSION_IS_ECMA(cx)) {
2007 /*
2008 * Deviate from ECMA to imitate Perl, which omits a final
2009 * split unless a limit argument is given and big enough.
2010 */
2011 if (!limited && (size_t)i == JSSTRING_LENGTH(str))
2012 break;
2013 }
2014 }
2015 ok = (j != -2);
2016 }
2017 return ok;
2018 }
2020 #if JS_HAS_PERL_SUBSTR
2021 static JSBool
2022 str_substr(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2023 {
2024 JSString *str;
2025 jsdouble d;
2026 jsdouble length, begin, end;
2028 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
2029 if (!str)
2030 return JS_FALSE;
2031 argv[-1] = STRING_TO_JSVAL(str);
2033 if (argc != 0) {
2034 if (!js_ValueToNumber(cx, argv[0], &d))
2035 return JS_FALSE;
2036 length = JSSTRING_LENGTH(str);
2037 begin = js_DoubleToInteger(d);
2038 if (begin < 0) {
2039 begin += length;
2040 if (begin < 0)
2041 begin = 0;
2042 } else if (begin > length) {
2043 begin = length;
2044 }
2046 if (argc == 1) {
2047 end = length;
2048 } else {
2049 if (!js_ValueToNumber(cx, argv[1], &d))
2050 return JS_FALSE;
2051 end = js_DoubleToInteger(d);
2052 if (end < 0)
2053 end = 0;
2054 end += begin;
2055 if (end > length)
2056 end = length;
2057 }
2059 str = js_NewDependentString(cx, str, (size_t)begin,
2060 (size_t)(end - begin), 0);
2061 if (!str)
2062 return JS_FALSE;
2063 }
2064 *rval = STRING_TO_JSVAL(str);
2065 return JS_TRUE;
2066 }
2067 #endif /* JS_HAS_PERL_SUBSTR */
2069 #if JS_HAS_SEQUENCE_OPS
2070 /*
2071 * Python-esque sequence operations.
2072 */
2073 static JSBool
2074 str_concat(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2075 {
2076 JSString *str, *str2;
2077 uintN i;
2079 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
2080 if (!str)
2081 return JS_FALSE;
2082 argv[-1] = STRING_TO_JSVAL(str);
2084 for (i = 0; i < argc; i++) {
2085 str2 = js_ValueToString(cx, argv[i]);
2086 if (!str2)
2087 return JS_FALSE;
2088 argv[i] = STRING_TO_JSVAL(str2);
2090 str = js_ConcatStrings(cx, str, str2);
2091 if (!str)
2092 return JS_FALSE;
2093 }
2095 *rval = STRING_TO_JSVAL(str);
2096 return JS_TRUE;
2097 }
2099 static JSBool
2100 str_slice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2101 {
2102 JSString *str;
2103 jsdouble d;
2104 jsdouble length, begin, end;
2106 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
2107 if (!str)
2108 return JS_FALSE;
2109 argv[-1] = STRING_TO_JSVAL(str);
2111 if (argc != 0) {
2112 if (!js_ValueToNumber(cx, argv[0], &d))
2113 return JS_FALSE;
2114 length = JSSTRING_LENGTH(str);
2115 begin = js_DoubleToInteger(d);
2116 if (begin < 0) {
2117 begin += length;
2118 if (begin < 0)
2119 begin = 0;
2120 } else if (begin > length) {
2121 begin = length;
2122 }
2124 if (argc == 1) {
2125 end = length;
2126 } else {
2127 if (!js_ValueToNumber(cx, argv[1], &d))
2128 return JS_FALSE;
2129 end = js_DoubleToInteger(d);
2130 if (end < 0) {
2131 end += length;
2132 if (end < 0)
2133 end = 0;
2134 } else if (end > length) {
2135 end = length;
2136 }
2137 if (end < begin)
2138 end = begin;
2139 }
2141 str = js_NewDependentString(cx, str, (size_t)begin,
2142 (size_t)(end - begin), 0);
2143 if (!str)
2144 return JS_FALSE;
2145 }
2146 *rval = STRING_TO_JSVAL(str);
2147 return JS_TRUE;
2148 }
2149 #endif /* JS_HAS_SEQUENCE_OPS */
2151 #if JS_HAS_STR_HTML_HELPERS
2152 /*
2153 * HTML composition aids.
2154 */
2155 static JSBool
2156 tagify(JSContext *cx, JSObject *obj, jsval *argv,
2157 const char *begin, JSString *param, const char *end,
2158 jsval *rval)
2159 {
2160 JSString *str;
2161 jschar *tagbuf;
2162 size_t beglen, endlen, parlen, taglen;
2163 size_t i, j;
2165 str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
2166 if (!str)
2167 return JS_FALSE;
2168 argv[-1] = STRING_TO_JSVAL(str);
2170 if (!end)
2171 end = begin;
2173 beglen = strlen(begin);
2174 taglen = 1 + beglen + 1; /* '<begin' + '>' */
2175 parlen = 0; /* Avoid warning. */
2176 if (param) {
2177 parlen = JSSTRING_LENGTH(param);
2178 taglen += 2 + parlen + 1; /* '="param"' */
2179 }
2180 endlen = strlen(end);
2181 taglen += JSSTRING_LENGTH(str) + 2 + endlen + 1; /* 'str</end>' */
2183 if (taglen >= ~(size_t)0 / sizeof(jschar)) {
2184 JS_ReportOutOfMemory(cx);
2185 return JS_FALSE;
2186 }
2188 tagbuf = (jschar *) JS_malloc(cx, (taglen + 1) * sizeof(jschar));
2189 if (!tagbuf)
2190 return JS_FALSE;
2192 j = 0;
2193 tagbuf[j++] = '<';
2194 for (i = 0; i < beglen; i++)
2195 tagbuf[j++] = (jschar)begin[i];
2196 if (param) {
2197 tagbuf[j++] = '=';
2198 tagbuf[j++] = '"';
2199 js_strncpy(&tagbuf[j], JSSTRING_CHARS(param), parlen);
2200 j += parlen;
2201 tagbuf[j++] = '"';
2202 }
2203 tagbuf[j++] = '>';
2204 js_strncpy(&tagbuf[j], JSSTRING_CHARS(str), JSSTRING_LENGTH(str));
2205 j += JSSTRING_LENGTH(str);
2206 tagbuf[j++] = '<';
2207 tagbuf[j++] = '/';
2208 for (i = 0; i < endlen; i++)
2209 tagbuf[j++] = (jschar)end[i];
2210 tagbuf[j++] = '>';
2211 JS_ASSERT(j == taglen);
2212 tagbuf[j] = 0;
2214 str = js_NewString(cx, tagbuf, taglen, 0);
2215 if (!str) {
2216 free((char *)tagbuf);
2217 return JS_FALSE;
2218 }
2219 *rval = STRING_TO_JSVAL(str);
2220 return JS_TRUE;
2221 }
2223 static JSBool
2224 tagify_value(JSContext *cx, JSObject *obj, jsval *argv,
2225 const char *begin, const char *end,
2226 jsval *rval)
2227 {
2228 JSString *param;
2230 param = js_ValueToString(cx, argv[0]);
2231 if (!param)
2232 return JS_FALSE;
2233 argv[0] = STRING_TO_JSVAL(param);
2234 return tagify(cx, obj, argv, begin, param, end, rval);
2235 }
2237 static JSBool
2238 str_bold(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2239 {
2240 return tagify(cx, obj, argv, "b", NULL, NULL, rval);
2241 }
2243 static JSBool
2244 str_italics(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2245 {
2246 return tagify(cx, obj, argv, "i", NULL, NULL, rval);
2247 }
2249 static JSBool
2250 str_fixed(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2251 {
2252 return tagify(cx, obj, argv, "tt", NULL, NULL, rval);
2253 }
2255 static JSBool
2256 str_fontsize(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2257 {
2258 return tagify_value(cx, obj, argv, "font size", "font", rval);
2259 }
2261 static JSBool
2262 str_fontcolor(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
2263 jsval *rval)
2264 {
2265 return tagify_value(cx, obj, argv, "font color", "font", rval);
2266 }
2268 static JSBool
2269 str_link(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2270 {
2271 return tagify_value(cx, obj, argv, "a href", "a", rval);
2272 }
2274 static JSBool
2275 str_anchor(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2276 {
2277 return tagify_value(cx, obj, argv, "a name", "a", rval);
2278 }
2280 static JSBool
2281 str_strike(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2282 {
2283 return tagify(cx, obj, argv, "strike", NULL, NULL, rval);
2284 }
2286 static JSBool
2287 str_small(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2288 {
2289 return tagify(cx, obj, argv, "small", NULL, NULL, rval);
2290 }
2292 static JSBool
2293 str_big(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2294 {
2295 return tagify(cx, obj, argv, "big", NULL, NULL, rval);
2296 }
2298 static JSBool
2299 str_blink(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2300 {
2301 return tagify(cx, obj, argv, "blink", NULL, NULL, rval);
2302 }
2304 static JSBool
2305 str_sup(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2306 {
2307 return tagify(cx, obj, argv, "sup", NULL, NULL, rval);
2308 }
2310 static JSBool
2311 str_sub(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2312 {
2313 return tagify(cx, obj, argv, "sub", NULL, NULL, rval);
2314 }
2315 #endif /* JS_HAS_STR_HTML_HELPERS */
2317 static JSFunctionSpec string_methods[] = {
2318 #if JS_HAS_TOSOURCE
2319 {"quote", str_quote, 0,JSFUN_GENERIC_NATIVE,0},
2320 {js_toSource_str, str_toSource, 0,0,0},
2321 #endif
2323 /* Java-like methods. */
2324 {js_toString_str, str_toString, 0,0,0},
2325 {js_valueOf_str, str_valueOf, 0,0,0},
2326 {"substring", str_substring, 2,JSFUN_GENERIC_NATIVE,0},
2327 {"toLowerCase", str_toLowerCase, 0,JSFUN_GENERIC_NATIVE,0},
2328 {"toUpperCase", str_toUpperCase, 0,JSFUN_GENERIC_NATIVE,0},
2329 {"charAt", str_charAt, 1,JSFUN_GENERIC_NATIVE,0},
2330 {"charCodeAt", str_charCodeAt, 1,JSFUN_GENERIC_NATIVE,0},
2331 {"indexOf", str_indexOf, 1,JSFUN_GENERIC_NATIVE,0},
2332 {"lastIndexOf", str_lastIndexOf, 1,JSFUN_GENERIC_NATIVE,0},
2333 {"toLocaleLowerCase", str_toLocaleLowerCase, 0,JSFUN_GENERIC_NATIVE,0},
2334 {"toLocaleUpperCase", str_toLocaleUpperCase, 0,JSFUN_GENERIC_NATIVE,0},
2335 {"localeCompare", str_localeCompare, 1,JSFUN_GENERIC_NATIVE,0},
2337 /* Perl-ish methods (search is actually Python-esque). */
2338 #if JS_HAS_REGEXPS
2339 {"match", str_match, 1,JSFUN_GENERIC_NATIVE,2},
2340 {"search", str_search, 1,JSFUN_GENERIC_NATIVE,0},
2341 {"replace", str_replace, 2,JSFUN_GENERIC_NATIVE,0},
2342 {"split", str_split, 2,JSFUN_GENERIC_NATIVE,0},
2343 #endif
2344 #if JS_HAS_PERL_SUBSTR
2345 {"substr", str_substr, 2,JSFUN_GENERIC_NATIVE,0},
2346 #endif
2348 /* Python-esque sequence methods. */
2349 #if JS_HAS_SEQUENCE_OPS
2350 {"concat", str_concat, 0,JSFUN_GENERIC_NATIVE,0},
2351 {"slice", str_slice, 0,JSFUN_GENERIC_NATIVE,0},
2352 #endif
2354 /* HTML string methods. */
2355 #if JS_HAS_STR_HTML_HELPERS
2356 {"bold", str_bold, 0,0,0},
2357 {"italics", str_italics, 0,0,0},
2358 {"fixed", str_fixed, 0,0,0},
2359 {"fontsize", str_fontsize, 1,0,0},
2360 {"fontcolor", str_fontcolor, 1,0,0},
2361 {"link", str_link, 1,0,0},
2362 {"anchor", str_anchor, 1,0,0},
2363 {"strike", str_strike, 0,0,0},
2364 {"small", str_small, 0,0,0},
2365 {"big", str_big, 0,0,0},
2366 {"blink", str_blink, 0,0,0},
2367 {"sup", str_sup, 0,0,0},
2368 {"sub", str_sub, 0,0,0},
2369 #endif
2371 {0,0,0,0,0}
2372 };
2374 static JSBool
2375 String(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2376 {
2377 JSString *str;
2379 if (argc > 0) {
2380 str = js_ValueToString(cx, argv[0]);
2381 if (!str)
2382 return JS_FALSE;
2383 argv[0] = STRING_TO_JSVAL(str);
2384 } else {
2385 str = cx->runtime->emptyString;
2386 }
2387 if (!(cx->fp->flags & JSFRAME_CONSTRUCTING)) {
2388 *rval = STRING_TO_JSVAL(str);
2389 return JS_TRUE;
2390 }
2391 OBJ_SET_SLOT(cx, obj, JSSLOT_PRIVATE, STRING_TO_JSVAL(str));
2392 return JS_TRUE;
2393 }
2395 static JSBool
2396 str_fromCharCode(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
2397 jsval *rval)
2398 {
2399 jschar *chars;
2400 uintN i;
2401 uint16 code;
2402 JSString *str;
2404 chars = (jschar *) JS_malloc(cx, (argc + 1) * sizeof(jschar));
2405 if (!chars)
2406 return JS_FALSE;
2407 for (i = 0; i < argc; i++) {
2408 if (!js_ValueToUint16(cx, argv[i], &code)) {
2409 JS_free(cx, chars);
2410 return JS_FALSE;
2411 }
2412 chars[i] = (jschar)code;
2413 }
2414 chars[i] = 0;
2415 str = js_NewString(cx, chars, argc, 0);
2416 if (!str) {
2417 JS_free(cx, chars);
2418 return JS_FALSE;
2419 }
2420 *rval = STRING_TO_JSVAL(str);
2421 return JS_TRUE;
2422 }
2424 static JSFunctionSpec string_static_methods[] = {
2425 {"fromCharCode", str_fromCharCode, 1,0,0},
2426 {0,0,0,0,0}
2427 };
2429 static JSHashTable *deflated_string_cache;
2430 #ifdef DEBUG
2431 static uint32 deflated_string_cache_bytes;
2432 #endif
2433 #ifdef JS_THREADSAFE
2434 static JSLock *deflated_string_cache_lock;
2435 #endif
2437 JSBool
2438 js_InitStringGlobals(void)
2439 {
2440 #ifdef JS_THREADSAFE
2441 /* Must come through here once in primordial thread to init safely! */
2442 if (!deflated_string_cache_lock) {
2443 deflated_string_cache_lock = JS_NEW_LOCK();
2444 if (!deflated_string_cache_lock)
2445 return JS_FALSE;
2446 }
2447 #endif
2448 return JS_TRUE;
2449 }
2451 void
2452 js_FreeStringGlobals()
2453 {
2454 if (deflated_string_cache) {
2455 JS_HashTableDestroy(deflated_string_cache);
2456 deflated_string_cache = NULL;
2457 }
2458 #ifdef JS_THREADSAFE
2459 if (deflated_string_cache_lock) {
2460 JS_DESTROY_LOCK(deflated_string_cache_lock);
2461 deflated_string_cache_lock = NULL;
2462 }
2463 #endif
2464 }
2466 JSBool
2467 js_InitRuntimeStringState(JSContext *cx)
2468 {
2469 JSRuntime *rt;
2470 JSString *empty;
2471 JSAtom *atom;
2473 rt = cx->runtime;
2474 JS_ASSERT(!rt->emptyString);
2476 /* Make a permanently locked empty string. */
2477 empty = js_NewStringCopyN(cx, js_empty_ucstr, 0, GCF_LOCK);
2478 if (!empty)
2479 return JS_FALSE;
2481 /* Atomize it for scripts that use '' + x to convert x to string. */
2482 atom = js_AtomizeString(cx, empty, ATOM_PINNED);
2483 if (!atom)
2484 return JS_FALSE;
2486 rt->emptyString = empty;
2487 rt->atomState.emptyAtom = atom;
2488 return JS_TRUE;
2489 }
2491 void
2492 js_FinishRuntimeStringState(JSContext *cx)
2493 {
2494 JSRuntime *rt = cx->runtime;
2496 js_UnlockGCThingRT(rt, rt->emptyString);
2497 rt->emptyString = NULL;
2498 }
2500 JSObject *
2501 js_InitStringClass(JSContext *cx, JSObject *obj)
2502 {
2503 JSObject *proto;
2505 /* Define the escape, unescape functions in the global object. */
2506 if (!JS_DefineFunctions(cx, obj, string_functions))
2507 return NULL;
2509 proto = JS_InitClass(cx, obj, NULL, &js_StringClass, String, 1,
2510 string_props, string_methods,
2511 NULL, string_static_methods);
2512 if (!proto)
2513 return NULL;
2514 OBJ_SET_SLOT(cx, proto, JSSLOT_PRIVATE,
2515 STRING_TO_JSVAL(cx->runtime->emptyString));
2516 return proto;
2517 }
2519 JSString *
2520 js_NewString(JSContext *cx, jschar *chars, size_t length, uintN gcflag)
2521 {
2522 JSString *str;
2524 if (length > JSSTRING_LENGTH_MASK) {
2525 JS_ReportOutOfMemory(cx);
2526 return NULL;
2527 }
2529 str = (JSString *) js_NewGCThing(cx, gcflag | GCX_STRING, sizeof(JSString));
2530 if (!str)
2531 return NULL;
2532 str->length = length;
2533 str->chars = chars;
2534 #ifdef DEBUG
2535 {
2536 JSRuntime *rt = cx->runtime;
2537 JS_RUNTIME_METER(rt, liveStrings);
2538 JS_RUNTIME_METER(rt, totalStrings);
2539 JS_LOCK_RUNTIME_VOID(rt,
2540 (rt->lengthSum += (double)length,
2541 rt->lengthSquaredSum += (double)length * (double)length));
2542 }
2543 #endif
2544 return str;
2545 }
2547 JSString *
2548 js_NewDependentString(JSContext *cx, JSString *base, size_t start,
2549 size_t length, uintN gcflag)
2550 {
2551 JSDependentString *ds;
2553 if (length == 0)
2554 return cx->runtime->emptyString;
2556 if (start == 0 && length == JSSTRING_LENGTH(base))
2557 return base;
2559 if (start > JSSTRDEP_START_MASK ||
2560 (start != 0 && length > JSSTRDEP_LENGTH_MASK)) {
2561 return js_NewStringCopyN(cx, JSSTRING_CHARS(base) + start, length,
2562 gcflag);
2563 }
2565 ds = (JSDependentString *)
2566 js_NewGCThing(cx, gcflag | GCX_MUTABLE_STRING, sizeof(JSString));
2567 if (!ds)
2568 return NULL;
2569 if (start == 0) {
2570 JSPREFIX_SET_LENGTH(ds, length);
2571 JSPREFIX_SET_BASE(ds, base);
2572 } else {
2573 JSSTRDEP_SET_START_AND_LENGTH(ds, start, length);
2574 JSSTRDEP_SET_BASE(ds, base);
2575 }
2576 #ifdef DEBUG
2577 {
2578 JSRuntime *rt = cx->runtime;
2579 JS_RUNTIME_METER(rt, liveDependentStrings);
2580 JS_RUNTIME_METER(rt, totalDependentStrings);
2581 JS_RUNTIME_METER(rt, liveStrings);
2582 JS_RUNTIME_METER(rt, totalStrings);
2583 JS_LOCK_RUNTIME_VOID(rt,
2584 (rt->strdepLengthSum += (double)length,
2585 rt->strdepLengthSquaredSum += (double)length * (double)length));
2586 JS_LOCK_RUNTIME_VOID(rt,
2587 (rt->lengthSum += (double)length,
2588 rt->lengthSquaredSum += (double)length * (double)length));
2589 }
2590 #endif
2591 return (JSString *)ds;
2592 }
2594 #ifdef DEBUG
2595 #include <math.h>
2597 void printJSStringStats(JSRuntime *rt) {
2598 double mean = 0., var = 0., sigma = 0.;
2599 jsrefcount count = rt->totalStrings;
2600 if (count > 0 && rt->lengthSum >= 0) {
2601 mean = rt->lengthSum / count;
2602 var = count * rt->lengthSquaredSum - rt->lengthSum * rt->lengthSum;
2603 if (var < 0.0 || count <= 1)
2604 var = 0.0;
2605 else
2606 var /= count * (count - 1);
2608 /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
2609 sigma = (var != 0.) ? sqrt(var) : 0.;
2610 }
2611 fprintf(stderr, "%lu total strings, mean length %g (sigma %g)\n",
2612 (unsigned long)count, mean, sigma);
2614 mean = var = sigma = 0.;
2615 count = rt->totalDependentStrings;
2616 if (count > 0 && rt->strdepLengthSum >= 0) {
2617 mean = rt->strdepLengthSum / count;
2618 var = count * rt->strdepLengthSquaredSum
2619 - rt->strdepLengthSum * rt->strdepLengthSum;
2620 if (var < 0.0 || count <= 1)
2621 var = 0.0;
2622 else
2623 var /= count * (count - 1);
2625 /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
2626 sigma = (var != 0.) ? sqrt(var) : 0.;
2627 }
2628 fprintf(stderr, "%lu total dependent strings, mean length %g (sigma %g)\n",
2629 (unsigned long)count, mean, sigma);
2630 }
2631 #endif
2633 JSString *
2634 js_NewStringCopyN(JSContext *cx, const jschar *s, size_t n, uintN gcflag)
2635 {
2636 jschar *news;
2637 JSString *str;
2639 news = (jschar *)JS_malloc(cx, (n + 1) * sizeof(jschar));
2640 if (!news)
2641 return NULL;
2642 js_strncpy(news, s, n);
2643 news[n] = 0;
2644 str = js_NewString(cx, news, n, gcflag);
2645 if (!str)
2646 JS_free(cx, news);
2647 return str;
2648 }
2650 JSString *
2651 js_NewStringCopyZ(JSContext *cx, const jschar *s, uintN gcflag)
2652 {
2653 size_t n, m;
2654 jschar *news;
2655 JSString *str;
2657 n = js_strlen(s);
2658 m = (n + 1) * sizeof(jschar);
2659 news = (jschar *) JS_malloc(cx, m);
2660 if (!news)
2661 return NULL;
2662 memcpy(news, s, m);
2663 str = js_NewString(cx, news, n, gcflag);
2664 if (!str)
2665 JS_free(cx, news);
2666 return str;
2667 }
2669 JS_STATIC_DLL_CALLBACK(JSHashNumber)
2670 js_hash_string_pointer(const void *key)
2671 {
2672 return (JSHashNumber)JS_PTR_TO_UINT32(key) >> JSVAL_TAGBITS;
2673 }
2675 void
2676 js_PurgeDeflatedStringCache(JSString *str)
2677 {
2678 JSHashNumber hash;
2679 JSHashEntry *he, **hep;
2681 if (!deflated_string_cache)
2682 return;
2684 hash = js_hash_string_pointer(str);
2685 JS_ACQUIRE_LOCK(deflated_string_cache_lock);
2686 hep = JS_HashTableRawLookup(deflated_string_cache, hash, str);
2687 he = *hep;
2688 if (he) {
2689 #ifdef DEBUG
2690 deflated_string_cache_bytes -= JSSTRING_LENGTH(str);
2691 #endif
2692 free(he->value);
2693 JS_HashTableRawRemove(deflated_string_cache, hep, he);
2694 }
2695 JS_RELEASE_LOCK(deflated_string_cache_lock);
2696 }
2698 void
2699 js_FinalizeString(JSContext *cx, JSString *str)
2700 {
2701 js_FinalizeStringRT(cx->runtime, str);
2702 }
2704 void
2705 js_FinalizeStringRT(JSRuntime *rt, JSString *str)
2706 {
2707 JSBool valid;
2709 JS_RUNTIME_UNMETER(rt, liveStrings);
2710 if (JSSTRING_IS_DEPENDENT(str)) {
2711 /* If JSSTRFLAG_DEPENDENT is set, this string must be valid. */
2712 JS_ASSERT(JSSTRDEP_BASE(str));
2713 JS_RUNTIME_UNMETER(rt, liveDependentStrings);
2714 valid = JS_TRUE;
2715 } else {
2716 /* A stillborn string has null chars, so is not valid. */
2717 valid = (str->chars != NULL);
2718 if (valid)
2719 free(str->chars);
2720 }
2721 if (valid) {
2722 js_PurgeDeflatedStringCache(str);
2723 str->chars = NULL;
2724 }
2725 str->length = 0;
2726 }
2728 JSObject *
2729 js_StringToObject(JSContext *cx, JSString *str)
2730 {
2731 JSObject *obj;
2733 obj = js_NewObject(cx, &js_StringClass, NULL, NULL);
2734 if (!obj)
2735 return NULL;
2736 OBJ_SET_SLOT(cx, obj, JSSLOT_PRIVATE, STRING_TO_JSVAL(str));
2737 return obj;
2738 }
2740 JS_FRIEND_API(const char *)
2741 js_ValueToPrintableString(JSContext *cx, jsval v)
2742 {
2743 JSString *str;
2744 const char *bytes;
2746 str = js_ValueToString(cx, v);
2747 if (!str)
2748 return NULL;
2749 str = js_QuoteString(cx, str, 0);
2750 if (!str)
2751 return NULL;
2752 bytes = js_GetStringBytes(str);
2753 if (!bytes)
2754 JS_ReportOutOfMemory(cx);
2755 return bytes;
2756 }
2758 JSString *
2759 js_ValueToString(JSContext *cx, jsval v)
2760 {
2761 JSObject *obj;
2762 JSString *str;
2764 if (JSVAL_IS_OBJECT(v)) {
2765 obj = JSVAL_TO_OBJECT(v);
2766 if (!obj)
2767 return ATOM_TO_STRING(cx->runtime->atomState.nullAtom);
2768 if (!OBJ_DEFAULT_VALUE(cx, obj, JSTYPE_STRING, &v))
2769 return NULL;
2770 }
2771 if (JSVAL_IS_STRING(v)) {
2772 str = JSVAL_TO_STRING(v);
2773 } else if (JSVAL_IS_INT(v)) {
2774 str = js_NumberToString(cx, JSVAL_TO_INT(v));
2775 } else if (JSVAL_IS_DOUBLE(v)) {
2776 str = js_NumberToString(cx, *JSVAL_TO_DOUBLE(v));
2777 } else if (JSVAL_IS_BOOLEAN(v)) {
2778 str = js_BooleanToString(cx, JSVAL_TO_BOOLEAN(v));
2779 } else {
2780 str = ATOM_TO_STRING(cx->runtime->atomState.typeAtoms[JSTYPE_VOID]);
2781 }
2782 return str;
2783 }
2785 JSString *
2786 js_ValueToSource(JSContext *cx, jsval v)
2787 {
2788 JSTempValueRooter tvr;
2789 JSString *str;
2791 if (JSVAL_IS_STRING(v))
2792 return js_QuoteString(cx, JSVAL_TO_STRING(v), '"');
2793 if (JSVAL_IS_PRIMITIVE(v)) {
2794 /* Special case to preserve negative zero, _contra_ toString. */
2795 if (JSVAL_IS_DOUBLE(v) && JSDOUBLE_IS_NEGZERO(*JSVAL_TO_DOUBLE(v))) {
2796 /* NB: _ucNstr rather than _ucstr to indicate non-terminated. */
2797 static const jschar js_negzero_ucNstr[] = {'-', '0'};
2799 return js_NewStringCopyN(cx, js_negzero_ucNstr, 2, 0);
2800 }
2801 return js_ValueToString(cx, v);
2802 }
2804 JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
2805 if (!js_TryMethod(cx, JSVAL_TO_OBJECT(v),
2806 cx->runtime->atomState.toSourceAtom,
2807 0, NULL, &tvr.u.value)) {
2808 str = NULL;
2809 } else {
2810 str = js_ValueToString(cx, tvr.u.value);
2811 }
2812 JS_POP_TEMP_ROOT(cx, &tvr);
2813 return str;
2814 }
2816 JSHashNumber
2817 js_HashString(JSString *str)
2818 {
2819 JSHashNumber h;
2820 const jschar *s;
2821 size_t n;
2823 h = 0;
2824 for (s = JSSTRING_CHARS(str), n = JSSTRING_LENGTH(str); n; s++, n--)
2825 h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s;
2826 return h;
2827 }
2829 intN
2830 js_CompareStrings(JSString *str1, JSString *str2)
2831 {
2832 size_t l1, l2, n, i;
2833 const jschar *s1, *s2;
2834 intN cmp;
2836 l1 = JSSTRING_LENGTH(str1), l2 = JSSTRING_LENGTH(str2);
2837 s1 = JSSTRING_CHARS(str1), s2 = JSSTRING_CHARS(str2);
2838 n = JS_MIN(l1, l2);
2839 for (i = 0; i < n; i++) {
2840 cmp = s1[i] - s2[i];
2841 if (cmp != 0)
2842 return cmp;
2843 }
2844 return (intN)(l1 - l2);
2845 }
2847 size_t
2848 js_strlen(const jschar *s)
2849 {
2850 const jschar *t;
2852 for (t = s; *t != 0; t++)
2853 continue;
2854 return (size_t)(t - s);
2855 }
2857 jschar *
2858 js_strchr(const jschar *s, jschar c)
2859 {
2860 while (*s != 0) {
2861 if (*s == c)
2862 return (jschar *)s;
2863 s++;
2864 }
2865 return NULL;
2866 }
2868 jschar *
2869 js_strchr_limit(const jschar *s, jschar c, const jschar *limit)
2870 {
2871 while (s < limit) {
2872 if (*s == c)
2873 return (jschar *)s;
2874 s++;
2875 }
2876 return NULL;
2877 }
2879 const jschar *
2880 js_SkipWhiteSpace(const jschar *s)
2881 {
2882 /* JS_ISSPACE is false on a null. */
2883 while (JS_ISSPACE(*s))
2884 s++;
2885 return s;
2886 }
2888 #ifdef JS_C_STRINGS_ARE_UTF8
2890 jschar *
2891 js_InflateString(JSContext *cx, const char *bytes, size_t *length)
2892 {
2893 jschar *chars = NULL;
2894 size_t dstlen = 0;
2896 if (!js_InflateStringToBuffer(cx, bytes, *length, NULL, &dstlen))
2897 return NULL;
2898 chars = (jschar *) JS_malloc(cx, (dstlen + 1) * sizeof (jschar));
2899 if (!chars)
2900 return NULL;
2901 js_InflateStringToBuffer(cx, bytes, *length, chars, &dstlen);
2902 chars[dstlen] = 0;
2903 *length = dstlen;
2904 return chars;
2905 }
2907 /*
2908 * May be called with null cx by js_GetStringBytes, see below.
2909 */
2910 char *
2911 js_DeflateString(JSContext *cx, const jschar *chars, size_t length)
2912 {
2913 size_t size = 0;
2914 char *bytes = NULL;
2915 if (!js_DeflateStringToBuffer(cx, chars, length, NULL, &size))
2916 return NULL;
2917 bytes = (char *) (cx ? JS_malloc(cx, size+1) : malloc(size+1));
2918 if (!bytes)
2919 return NULL;
2920 js_DeflateStringToBuffer(cx, chars, length, bytes, &size);
2921 bytes[size] = 0;
2922 return bytes;
2923 }
2925 JSBool
2926 js_DeflateStringToBuffer(JSContext *cx, const jschar *src, size_t srclen,
2927 char *dst, size_t *dstlenp)
2928 {
2929 size_t i, utf8Len, dstlen = *dstlenp, origDstlen = dstlen;
2930 jschar c, c2;
2931 uint32 v;
2932 uint8 utf8buf[6];
2934 if (!dst)
2935 dstlen = origDstlen = (size_t) -1;
2937 while (srclen) {
2938 c = *src++;
2939 srclen--;
2940 if ((c >= 0xDC00) && (c <= 0xDFFF))
2941 goto badSurrogate;
2942 if (c < 0xD800 || c > 0xDBFF) {
2943 v = c;
2944 } else {
2945 if (srclen < 1)
2946 goto bufferTooSmall;
2947 c2 = *src++;
2948 srclen--;
2949 if ((c2 < 0xDC00) || (c2 > 0xDFFF)) {
2950 c = c2;
2951 goto badSurrogate;
2952 }
2953 v = ((c - 0xD800) << 10) + (c2 - 0xDC00) + 0x10000;
2954 }
2955 if (v < 0x0080) {
2956 /* no encoding necessary - performance hack */
2957 if (!dstlen)
2958 goto bufferTooSmall;
2959 if (dst)
2960 *dst++ = (char) v;
2961 utf8Len = 1;
2962 } else {
2963 utf8Len = js_OneUcs4ToUtf8Char(utf8buf, v);
2964 if (utf8Len > dstlen)
2965 goto bufferTooSmall;
2966 if (dst) {
2967 for (i = 0; i < utf8Len; i++)
2968 *dst++ = (char) utf8buf[i];
2969 }
2970 }
2971 dstlen -= utf8Len;
2972 }
2973 *dstlenp = (origDstlen - dstlen);
2974 return JS_TRUE;
2976 badSurrogate:
2977 *dstlenp = (origDstlen - dstlen);
2978 if (cx) {
2979 char buffer[10];
2980 JS_snprintf(buffer, 10, "0x%x", c);
2981 JS_ReportErrorFlagsAndNumber(cx, JSREPORT_ERROR,
2982 js_GetErrorMessage, NULL,
2983 JSMSG_BAD_SURROGATE_CHAR,
2984 buffer);
2985 }
2986 return JS_FALSE;
2988 bufferTooSmall:
2989 *dstlenp = (origDstlen - dstlen);
2990 if (cx) {
2991 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2992 JSMSG_BUFFER_TOO_SMALL);
2993 }
2994 return JS_FALSE;
2995 }
2997 JSBool
2998 js_InflateStringToBuffer(JSContext *cx, const char *src, size_t srclen,
2999 jschar *dst, size_t *dstlenp)
3000 {
3001 uint32 v;
3002 size_t offset = 0, j, n, dstlen = *dstlenp, origDstlen = dstlen;
3004 if (!dst)
3005 dstlen = origDstlen = (size_t) -1;
3007 while (srclen) {
3008 v = (uint8) *src;
3009 n = 1;
3010 if (v & 0x80) {
3011 while (v & (0x80 >> n))
3012 n++;
3013 if (n > srclen)
3014 goto bufferTooSmall;
3015 if (n == 1 || n > 6)
3016 goto badCharacter;
3017 for (j = 1; j < n; j++) {
3018 if ((src[j] & 0xC0) != 0x80)
3019 goto badCharacter;
3020 }
3021 v = Utf8ToOneUcs4Char(src, n);
3022 if (v >= 0x10000) {
3023 v -= 0x10000;
3024 if (v > 0xFFFFF || dstlen < 2) {
3025 *dstlenp = (origDstlen - dstlen);
3026 if (cx) {
3027 char buffer[10];
3028 JS_snprintf(buffer, 10, "0x%x", v + 0x10000);
3029 JS_ReportErrorFlagsAndNumber(cx,
3030 JSREPORT_ERROR,
3031 js_GetErrorMessage, NULL,
3032 JSMSG_UTF8_CHAR_TOO_LARGE,
3033 buffer);
3034 }
3035 return JS_FALSE;
3036 }
3037 if (dstlen < 2)
3038 goto bufferTooSmall;
3039 if (dst) {
3040 *dst++ = (jschar)((v >> 10) + 0xD800);
3041 v = (jschar)((v & 0x3FF) + 0xDC00);
3042 }
3043 dstlen--;
3044 }
3045 }
3046 if (!dstlen)
3047 goto bufferTooSmall;
3048 if (dst)
3049 *dst++ = (jschar) v;
3050 dstlen--;
3051 offset += n;
3052 src += n;
3053 srclen -= n;
3054 }
3055 *dstlenp = (origDstlen - dstlen);
3056 return JS_TRUE;
3058 badCharacter:
3059 *dstlenp = (origDstlen - dstlen);
3060 if (cx) {
3061 char buffer[10];
3062 JS_snprintf(buffer, 10, "%d", offset);
3063 JS_ReportErrorFlagsAndNumber(cx, JSREPORT_ERROR,
3064 js_GetErrorMessage, NULL,
3065 JSMSG_MALFORMED_UTF8_CHAR,
3066 buffer);
3067 }
3068 return JS_FALSE;
3070 bufferTooSmall:
3071 *dstlenp = (origDstlen - dstlen);
3072 if (cx) {
3073 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3074 JSMSG_BUFFER_TOO_SMALL);
3075 }
3076 return JS_FALSE;
3077 }
3079 #else /* !JS_C_STRINGS_ARE_UTF8 */
3081 JSBool
3082 js_InflateStringToBuffer(JSContext* cx, const char *bytes, size_t length,
3083 jschar *chars, size_t* charsLength)
3084 {
3085 size_t i;
3087 if (length > *charsLength) {
3088 for (i = 0; i < *charsLength; i++)
3089 chars[i] = (unsigned char) bytes[i];
3090 if (cx) {
3091 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3092 JSMSG_BUFFER_TOO_SMALL);
3093 }
3094 return JS_FALSE;
3095 }
3096 for (i = 0; i < length; i++)
3097 chars[i] = (unsigned char) bytes[i];
3098 *charsLength = length;
3099 return JS_TRUE;
3100 }
3102 jschar *
3103 js_InflateString(JSContext *cx, const char *bytes, size_t *bytesLength)
3104 {
3105 jschar *chars;
3106 size_t i, length = *bytesLength;
3108 chars = (jschar *) JS_malloc(cx, (length + 1) * sizeof(jschar));
3109 if (!chars) {
3110 *bytesLength = 0;
3111 return NULL;
3112 }
3113 for (i = 0; i < length; i++)
3114 chars[i] = (unsigned char) bytes[i];
3115 chars[length] = 0;
3116 *bytesLength = length;
3117 return chars;
3118 }
3120 JSBool
3121 js_DeflateStringToBuffer(JSContext* cx, const jschar *chars, size_t length,
3122 char *bytes, size_t* bytesLength)
3123 {
3124 size_t i;
3126 if (length > *bytesLength) {
3127 for (i = 0; i < *bytesLength; i++)
3128 bytes[i] = (char) chars[i];
3129 if (cx) {
3130 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3131 JSMSG_BUFFER_TOO_SMALL);
3132 }
3133 return JS_FALSE;
3134 }
3135 for (i = 0; i < length; i++)
3136 bytes[i] = (char) chars[i];
3137 *bytesLength = length;
3138 return JS_TRUE;
3139 }
3141 /*
3142 * May be called with null cx by js_GetStringBytes, see below.
3143 */
3144 char *
3145 js_DeflateString(JSContext *cx, const jschar *chars, size_t length)
3146 {
3147 size_t i, size;
3148 char *bytes;
3150 size = (length + 1) * sizeof(char);
3151 bytes = (char *) (cx ? JS_malloc(cx, size) : malloc(size));
3152 if (!bytes)
3153 return NULL;
3155 for (i = 0; i < length; i++)
3156 bytes[i] = (char) chars[i];
3158 bytes[length] = 0;
3159 return bytes;
3160 }
3162 #endif /* !JS_C_STRINGS_ARE_UTF8 */
3164 static JSHashTable *
3165 GetDeflatedStringCache(void)
3166 {
3167 JSHashTable *cache;
3169 cache = deflated_string_cache;
3170 if (!cache) {
3171 cache = JS_NewHashTable(8, js_hash_string_pointer,
3172 JS_CompareValues, JS_CompareValues,
3173 NULL, NULL);
3174 deflated_string_cache = cache;
3175 }
3176 return cache;
3177 }
3179 JSBool
3180 js_SetStringBytes(JSString *str, char *bytes, size_t length)
3181 {
3182 JSHashTable *cache;
3183 JSBool ok;
3184 JSHashNumber hash;
3185 JSHashEntry **hep;
3187 JS_ACQUIRE_LOCK(deflated_string_cache_lock);
3189 cache = GetDeflatedStringCache();
3190 if (!cache) {
3191 ok = JS_FALSE;
3192 } else {
3193 hash = js_hash_string_pointer(str);
3194 hep = JS_HashTableRawLookup(cache, hash, str);
3195 JS_ASSERT(*hep == NULL);
3196 ok = JS_HashTableRawAdd(cache, hep, hash, str, bytes) != NULL;
3197 #ifdef DEBUG
3198 if (ok)
3199 deflated_string_cache_bytes += length;
3200 #endif
3201 }
3203 JS_RELEASE_LOCK(deflated_string_cache_lock);
3204 return ok;
3205 }
3207 char *
3208 js_GetStringBytes(JSString *str)
3209 {
3210 JSHashTable *cache;
3211 char *bytes;
3212 JSHashNumber hash;
3213 JSHashEntry *he, **hep;
3215 JS_ACQUIRE_LOCK(deflated_string_cache_lock);
3217 cache = GetDeflatedStringCache();
3218 if (!cache) {
3219 bytes = NULL;
3220 } else {
3221 hash = js_hash_string_pointer(str);
3222 hep = JS_HashTableRawLookup(cache, hash, str);
3223 he = *hep;
3224 if (he) {
3225 bytes = (char *) he->value;
3227 /* Try to catch failure to JS_ShutDown between runtime epochs. */
3228 JS_ASSERT((*bytes == '\0' && JSSTRING_LENGTH(str) == 0) ||
3229 *bytes == (char) JSSTRING_CHARS(str)[0]);
3230 } else {
3231 bytes = js_DeflateString(NULL, JSSTRING_CHARS(str),
3232 JSSTRING_LENGTH(str));
3233 if (bytes) {
3234 if (JS_HashTableRawAdd(cache, hep, hash, str, bytes)) {
3235 #ifdef DEBUG
3236 deflated_string_cache_bytes += JSSTRING_LENGTH(str);
3237 #endif
3238 } else {
3239 free(bytes);
3240 bytes = NULL;
3241 }
3242 }
3243 }
3244 }
3246 JS_RELEASE_LOCK(deflated_string_cache_lock);
3247 return bytes;
3248 }
3250 /*
3251 * From java.lang.Character.java:
3252 *
3253 * The character properties are currently encoded into 32 bits in the
3254 * following manner:
3255 *
3256 * 10 bits signed offset used for converting case
3257 * 1 bit if 1, adding the signed offset converts the character to
3258 * lowercase
3259 * 1 bit if 1, subtracting the signed offset converts the character to
3260 * uppercase
3261 * 1 bit if 1, character has a titlecase equivalent (possibly itself)
3262 * 3 bits 0 may not be part of an identifier
3263 * 1 ignorable control; may continue a Unicode identifier or JS
3264 * identifier
3265 * 2 may continue a JS identifier but not a Unicode identifier
3266 * (unused)
3267 * 3 may continue a Unicode identifier or JS identifier
3268 * 4 is a JS whitespace character
3269 * 5 may start or continue a JS identifier;
3270 * may continue but not start a Unicode identifier (_)
3271 * 6 may start or continue a JS identifier but not a Unicode
3272 * identifier ($)
3273 * 7 may start or continue a Unicode identifier or JS identifier
3274 * Thus:
3275 * 5, 6, 7 may start a JS identifier
3276 * 1, 2, 3, 5, 6, 7 may continue a JS identifier
3277 * 7 may start a Unicode identifier
3278 * 1, 3, 5, 7 may continue a Unicode identifier
3279 * 1 is ignorable within an identifier
3280 * 4 is JS whitespace
3281 * 2 bits 0 this character has no numeric property
3282 * 1 adding the digit offset to the character code and then
3283 * masking with 0x1F will produce the desired numeric value
3284 * 2 this character has a "strange" numeric value
3285 * 3 a JS supradecimal digit: adding the digit offset to the
3286 * character code, then masking with 0x1F, then adding 10
3287 * will produce the desired numeric value
3288 * 5 bits digit offset
3289 * 1 bit XML 1.0 name start character
3290 * 1 bit XML 1.0 name character
3291 * 2 bits reserved for future use
3292 * 5 bits character type
3293 */
3295 /* The X table has 1024 entries for a total of 1024 bytes. */
3297 const uint8 js_X[] = {
3298 0, 1, 2, 3, 4, 5, 6, 7, /* 0x0000 */
3299 8, 9, 10, 11, 12, 13, 14, 15, /* 0x0200 */
3300 16, 17, 18, 19, 20, 21, 22, 23, /* 0x0400 */
3301 24, 25, 26, 27, 28, 28, 28, 28, /* 0x0600 */
3302 28, 28, 28, 28, 29, 30, 31, 32, /* 0x0800 */
3303 33, 34, 35, 36, 37, 38, 39, 40, /* 0x0A00 */
3304 41, 42, 43, 44, 45, 46, 28, 28, /* 0x0C00 */
3305 47, 48, 49, 50, 51, 52, 53, 28, /* 0x0E00 */
3306 28, 28, 54, 55, 56, 57, 58, 59, /* 0x1000 */
3307 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1200 */
3308 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1400 */
3309 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1600 */
3310 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1800 */
3311 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1A00 */
3312 28, 28, 28, 28, 28, 28, 28, 28, /* 0x1C00 */
3313 60, 60, 61, 62, 63, 64, 65, 66, /* 0x1E00 */
3314 67, 68, 69, 70, 71, 72, 73, 74, /* 0x2000 */
3315 75, 75, 75, 76, 77, 78, 28, 28, /* 0x2200 */
3316 79, 80, 81, 82, 83, 83, 84, 85, /* 0x2400 */
3317 86, 85, 28, 28, 87, 88, 89, 28, /* 0x2600 */
3318 28, 28, 28, 28, 28, 28, 28, 28, /* 0x2800 */
3319 28, 28, 28, 28, 28, 28, 28, 28, /* 0x2A00 */
3320 28, 28, 28, 28, 28, 28, 28, 28, /* 0x2C00 */
3321 28, 28, 28, 28, 28, 28, 28, 28, /* 0x2E00 */
3322 90, 91, 92, 93, 94, 56, 95, 28, /* 0x3000 */
3323 96, 97, 98, 99, 83, 100, 83, 101, /* 0x3200 */
3324 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3400 */
3325 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3600 */
3326 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3800 */
3327 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3A00 */
3328 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3C00 */
3329 28, 28, 28, 28, 28, 28, 28, 28, /* 0x3E00 */
3330 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4000 */
3331 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4200 */
3332 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4400 */
3333 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4600 */
3334 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4800 */
3335 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4A00 */
3336 28, 28, 28, 28, 28, 28, 28, 28, /* 0x4C00 */
3337 56, 56, 56, 56, 56, 56, 56, 56, /* 0x4E00 */
3338 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5000 */
3339 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5200 */
3340 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5400 */
3341 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5600 */
3342 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5800 */
3343 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5A00 */
3344 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5C00 */
3345 56, 56, 56, 56, 56, 56, 56, 56, /* 0x5E00 */
3346 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6000 */
3347 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6200 */
3348 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6400 */
3349 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6600 */
3350 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6800 */
3351 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6A00 */
3352 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6C00 */
3353 56, 56, 56, 56, 56, 56, 56, 56, /* 0x6E00 */
3354 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7000 */
3355 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7200 */
3356 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7400 */
3357 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7600 */
3358 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7800 */
3359 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7A00 */
3360 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7C00 */
3361 56, 56, 56, 56, 56, 56, 56, 56, /* 0x7E00 */
3362 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8000 */
3363 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8200 */
3364 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8400 */
3365 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8600 */
3366 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8800 */
3367 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8A00 */
3368 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8C00 */
3369 56, 56, 56, 56, 56, 56, 56, 56, /* 0x8E00 */
3370 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9000 */
3371 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9200 */
3372 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9400 */
3373 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9600 */
3374 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9800 */
3375 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9A00 */
3376 56, 56, 56, 56, 56, 56, 56, 56, /* 0x9C00 */
3377 56, 56, 56, 56, 56, 56, 102, 28, /* 0x9E00 */
3378 28, 28, 28, 28, 28, 28, 28, 28, /* 0xA000 */
3379 28, 28, 28, 28, 28, 28, 28, 28, /* 0xA200 */
3380 28, 28, 28, 28, 28, 28, 28, 28, /* 0xA400 */
3381 28, 28, 28, 28, 28, 28, 28, 28, /* 0xA600 */
3382 28, 28, 28, 28, 28, 28, 28, 28, /* 0xA800 */
3383 28, 28, 28, 28, 28, 28, 28, 28, /* 0xAA00 */
3384 56, 56, 56, 56, 56, 56, 56, 56, /* 0xAC00 */
3385 56, 56, 56, 56, 56, 56, 56, 56, /* 0xAE00 */
3386 56, 56, 56, 56, 56, 56, 56, 56, /* 0xB000 */
3387 56, 56, 56, 56, 56, 56, 56, 56, /* 0xB200 */
3388 56, 56, 56, 56, 56, 56, 56, 56, /* 0xB400 */
3389 56, 56, 56, 56, 56, 56, 56, 56, /* 0xB600 */
3390 56, 56, 56, 56, 56, 56, 56, 56, /* 0xB800 */
3391 56, 56, 56, 56, 56, 56, 56, 56, /* 0xBA00 */
3392 56, 56, 56, 56, 56, 56, 56, 56, /* 0xBC00 */
3393 56, 56, 56, 56, 56, 56, 56, 56, /* 0xBE00 */
3394 56, 56, 56, 56, 56, 56, 56, 56, /* 0xC000 */
3395 56, 56, 56, 56, 56, 56, 56, 56, /* 0xC200 */
3396 56, 56, 56, 56, 56, 56, 56, 56, /* 0xC400 */
3397 56, 56, 56, 56, 56, 56, 56, 56, /* 0xC600 */
3398 56, 56, 56, 56, 56, 56, 56, 56, /* 0xC800 */
3399 56, 56, 56, 56, 56, 56, 56, 56, /* 0xCA00 */
3400 56, 56, 56, 56, 56, 56, 56, 56, /* 0xCC00 */
3401 56, 56, 56, 56, 56, 56, 56, 56, /* 0xCE00 */
3402 56, 56, 56, 56, 56, 56, 56, 56, /* 0xD000 */
3403 56, 56, 56, 56, 56, 56, 56, 56, /* 0xD200 */
3404 56, 56, 56, 56, 56, 56, 56, 56, /* 0xD400 */
3405 56, 56, 56, 56, 56, 56, 103, 28, /* 0xD600 */
3406 104, 104, 104, 104, 104, 104, 104, 104, /* 0xD800 */
3407 104, 104, 104, 104, 104, 104, 104, 104, /* 0xDA00 */
3408 104, 104, 104, 104, 104, 104, 104, 104, /* 0xDC00 */
3409 104, 104, 104, 104, 104, 104, 104, 104, /* 0xDE00 */
3410 105, 105, 105, 105, 105, 105, 105, 105, /* 0xE000 */
3411 105, 105, 105, 105, 105, 105, 105, 105, /* 0xE200 */
3412 105, 105, 105, 105, 105, 105, 105, 105, /* 0xE400 */
3413 105, 105, 105, 105, 105, 105, 105, 105, /* 0xE600 */
3414 105, 105, 105, 105, 105, 105, 105, 105, /* 0xE800 */
3415 105, 105, 105, 105, 105, 105, 105, 105, /* 0xEA00 */
3416 105, 105, 105, 105, 105, 105, 105, 105, /* 0xEC00 */
3417 105, 105, 105, 105, 105, 105, 105, 105, /* 0xEE00 */
3418 105, 105, 105, 105, 105, 105, 105, 105, /* 0xF000 */
3419 105, 105, 105, 105, 105, 105, 105, 105, /* 0xF200 */
3420 105, 105, 105, 105, 105, 105, 105, 105, /* 0xF400 */
3421 105, 105, 105, 105, 105, 105, 105, 105, /* 0xF600 */
3422 105, 105, 105, 105, 56, 56, 56, 56, /* 0xF800 */
3423 106, 28, 28, 28, 107, 108, 109, 110, /* 0xFA00 */
3424 56, 56, 56, 56, 111, 112, 113, 114, /* 0xFC00 */
3425 115, 116, 56, 117, 118, 119, 120, 121 /* 0xFE00 */
3426 };
3428 /* The Y table has 7808 entries for a total of 7808 bytes. */
3430 const uint8 js_Y[] = {
3431 0, 0, 0, 0, 0, 0, 0, 0, /* 0 */
3432 0, 1, 1, 1, 1, 1, 0, 0, /* 0 */
3433 0, 0, 0, 0, 0, 0, 0, 0, /* 0 */
3434 0, 0, 0, 0, 0, 0, 0, 0, /* 0 */
3435 2, 3, 3, 3, 4, 3, 3, 3, /* 0 */
3436 5, 6, 3, 7, 3, 8, 3, 3, /* 0 */
3437 9, 9, 9, 9, 9, 9, 9, 9, /* 0 */
3438 9, 9, 3, 3, 7, 7, 7, 3, /* 0 */
3439 3, 10, 10, 10, 10, 10, 10, 10, /* 1 */
3440 10, 10, 10, 10, 10, 10, 10, 10, /* 1 */
3441 10, 10, 10, 10, 10, 10, 10, 10, /* 1 */
3442 10, 10, 10, 5, 3, 6, 11, 12, /* 1 */
3443 11, 13, 13, 13, 13, 13, 13, 13, /* 1 */
3444 13, 13, 13, 13, 13, 13, 13, 13, /* 1 */
3445 13, 13, 13, 13, 13, 13, 13, 13, /* 1 */
3446 13, 13, 13, 5, 7, 6, 7, 0, /* 1 */
3447 0, 0, 0, 0, 0, 0, 0, 0, /* 2 */
3448 0, 0, 0, 0, 0, 0, 0, 0, /* 2 */
3449 0, 0, 0, 0, 0, 0, 0, 0, /* 2 */
3450 0, 0, 0, 0, 0, 0, 0, 0, /* 2 */
3451 2, 3, 4, 4, 4, 4, 15, 15, /* 2 */
3452 11, 15, 16, 5, 7, 8, 15, 11, /* 2 */
3453 15, 7, 17, 17, 11, 16, 15, 3, /* 2 */
3454 11, 18, 16, 6, 19, 19, 19, 3, /* 2 */
3455 20, 20, 20, 20, 20, 20, 20, 20, /* 3 */
3456 20, 20, 20, 20, 20, 20, 20, 20, /* 3 */
3457 20, 20, 20, 20, 20, 20, 20, 7, /* 3 */
3458 20, 20, 20, 20, 20, 20, 20, 16, /* 3 */
3459 21, 21, 21, 21, 21, 21, 21, 21, /* 3 */
3460 21, 21, 21, 21, 21, 21, 21, 21, /* 3 */
3461 21, 21, 21, 21, 21, 21, 21, 7, /* 3 */
3462 21, 21, 21, 21, 21, 21, 21, 22, /* 3 */
3463 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3464 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3465 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3466 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3467 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3468 23, 24, 23, 24, 23, 24, 23, 24, /* 4 */
3469 25, 26, 23, 24, 23, 24, 23, 24, /* 4 */
3470 16, 23, 24, 23, 24, 23, 24, 23, /* 4 */
3471 24, 23, 24, 23, 24, 23, 24, 23, /* 5 */
3472 24, 16, 23, 24, 23, 24, 23, 24, /* 5 */
3473 23, 24, 23, 24, 23, 24, 23, 24, /* 5 */
3474 23, 24, 23, 24, 23, 24, 23, 24, /* 5 */
3475 23, 24, 23, 24, 23, 24, 23, 24, /* 5 */
3476 23, 24, 23, 24, 23, 24, 23, 24, /* 5 */
3477 23, 24, 23, 24, 23, 24, 23, 24, /* 5 */
3478 27, 23, 24, 23, 24, 23, 24, 28, /* 5 */
3479 16, 29, 23, 24, 23, 24, 30, 23, /* 6 */
3480 24, 31, 31, 23, 24, 16, 32, 32, /* 6 */
3481 33, 23, 24, 31, 34, 16, 35, 36, /* 6 */
3482 23, 24, 16, 16, 35, 37, 16, 38, /* 6 */
3483 23, 24, 23, 24, 23, 24, 38, 23, /* 6 */
3484 24, 39, 40, 16, 23, 24, 39, 23, /* 6 */
3485 24, 41, 41, 23, 24, 23, 24, 42, /* 6 */
3486 23, 24, 16, 40, 23, 24, 40, 40, /* 6 */
3487 40, 40, 40, 40, 43, 44, 45, 43, /* 7 */
3488 44, 45, 43, 44, 45, 23, 24, 23, /* 7 */
3489 24, 23, 24, 23, 24, 23, 24, 23, /* 7 */
3490 24, 23, 24, 23, 24, 16, 23, 24, /* 7 */
3491 23, 24, 23, 24, 23, 24, 23, 24, /* 7 */
3492 23, 24, 23, 24, 23, 24, 23, 24, /* 7 */
3493 16, 43, 44, 45, 23, 24, 46, 46, /* 7 */
3494 46, 46, 23, 24, 23, 24, 23, 24, /* 7 */
3495 23, 24, 23, 24, 23, 24, 23, 24, /* 8 */
3496 23, 24, 23, 24, 23, 24, 23, 24, /* 8 */
3497 23, 24, 23, 24, 23, 24, 23, 24, /* 8 */
3498 46, 46, 46, 46, 46, 46, 46, 46, /* 8 */
3499 46, 46, 46, 46, 46, 46, 46, 46, /* 8 */
3500 46, 46, 46, 46, 46, 46, 46, 46, /* 8 */
3501 46, 46, 46, 46, 46, 46, 46, 46, /* 8 */
3502 46, 46, 46, 46, 46, 46, 46, 46, /* 8 */
3503 46, 46, 46, 46, 46, 46, 46, 46, /* 9 */
3504 46, 46, 46, 46, 46, 46, 46, 46, /* 9 */
3505 16, 16, 16, 47, 48, 16, 49, 49, /* 9 */
3506 50, 50, 16, 51, 16, 16, 16, 16, /* 9 */
3507 49, 16, 16, 52, 16, 16, 16, 16, /* 9 */
3508 53, 54, 16, 16, 16, 16, 16, 54, /* 9 */
3509 16, 16, 55, 16, 16, 16, 16, 16, /* 9 */
3510 16, 16, 16, 16, 16, 16, 16, 16, /* 9 */
3511 16, 16, 16, 56, 16, 16, 16, 16, /* 10 */
3512 56, 16, 57, 57, 16, 16, 16, 16, /* 10 */
3513 16, 16, 58, 16, 16, 16, 16, 16, /* 10 */
3514 16, 16, 16, 16, 16, 16, 16, 16, /* 10 */
3515 16, 16, 16, 16, 16, 16, 16, 16, /* 10 */
3516 16, 46, 46, 46, 46, 46, 46, 46, /* 10 */
3517 59, 59, 59, 59, 59, 59, 59, 59, /* 10 */
3518 59, 11, 11, 59, 59, 59, 59, 59, /* 10 */
3519 59, 59, 11, 11, 11, 11, 11, 11, /* 11 */
3520 11, 11, 11, 11, 11, 11, 11, 11, /* 11 */
3521 59, 59, 11, 11, 11, 11, 11, 11, /* 11 */
3522 11, 11, 11, 11, 11, 11, 11, 46, /* 11 */
3523 59, 59, 59, 59, 59, 11, 11, 11, /* 11 */
3524 11, 11, 46, 46, 46, 46, 46, 46, /* 11 */
3525 46, 46, 46, 46, 46, 46, 46, 46, /* 11 */
3526 46, 46, 46, 46, 46, 46, 46, 46, /* 11 */
3527 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3528 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3529 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3530 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3531 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3532 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3533 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3534 60, 60, 60, 60, 60, 60, 60, 60, /* 12 */
3535 60, 60, 60, 60, 60, 60, 46, 46, /* 13 */
3536 46, 46, 46, 46, 46, 46, 46, 46, /* 13 */
3537 46, 46, 46, 46, 46, 46, 46, 46, /* 13 */
3538 46, 46, 46, 46, 46, 46, 46, 46, /* 13 */
3539 60, 60, 46, 46, 46, 46, 46, 46, /* 13 */
3540 46, 46, 46, 46, 46, 46, 46, 46, /* 13 */
3541 46, 46, 46, 46, 3, 3, 46, 46, /* 13 */
3542 46, 46, 59, 46, 46, 46, 3, 46, /* 13 */
3543 46, 46, 46, 46, 11, 11, 61, 3, /* 14 */
3544 62, 62, 62, 46, 63, 46, 64, 64, /* 14 */
3545 16, 20, 20, 20, 20, 20, 20, 20, /* 14 */
3546 20, 20, 20, 20, 20, 20, 20, 20, /* 14 */
3547 20, 20, 46, 20, 20, 20, 20, 20, /* 14 */
3548 20, 20, 20, 20, 65, 66, 66, 66, /* 14 */
3549 16, 21, 21, 21, 21, 21, 21, 21, /* 14 */
3550 21, 21, 21, 21, 21, 21, 21, 21, /* 14 */
3551 21, 21, 16, 21, 21, 21, 21, 21, /* 15 */
3552 21, 21, 21, 21, 67, 68, 68, 46, /* 15 */
3553 69, 70, 38, 38, 38, 71, 72, 46, /* 15 */
3554 46, 46, 38, 46, 38, 46, 38, 46, /* 15 */
3555 38, 46, 23, 24, 23, 24, 23, 24, /* 15 */
3556 23, 24, 23, 24, 23, 24, 23, 24, /* 15 */
3557 73, 74, 16, 40, 46, 46, 46, 46, /* 15 */
3558 46, 46, 46, 46, 46, 46, 46, 46, /* 15 */
3559 46, 75, 75, 75, 75, 75, 75, 75, /* 16 */
3560 75, 75, 75, 75, 75, 46, 75, 75, /* 16 */
3561 20, 20, 20, 20, 20, 20, 20, 20, /* 16 */
3562 20, 20, 20, 20, 20, 20, 20, 20, /* 16 */
3563 20, 20, 20, 20, 20, 20, 20, 20, /* 16 */
3564 20, 20, 20, 20, 20, 20, 20, 20, /* 16 */
3565 21, 21, 21, 21, 21, 21, 21, 21, /* 16 */
3566 21, 21, 21, 21, 21, 21, 21, 21, /* 16 */
3567 21, 21, 21, 21, 21, 21, 21, 21, /* 17 */
3568 21, 21, 21, 21, 21, 21, 21, 21, /* 17 */
3569 46, 74, 74, 74, 74, 74, 74, 74, /* 17 */
3570 74, 74, 74, 74, 74, 46, 74, 74, /* 17 */
3571 23, 24, 23, 24, 23, 24, 23, 24, /* 17 */
3572 23, 24, 23, 24, 23, 24, 23, 24, /* 17 */
3573 23, 24, 23, 24, 23, 24, 23, 24, /* 17 */
3574 23, 24, 23, 24, 23, 24, 23, 24, /* 17 */
3575 23, 24, 15, 60, 60, 60, 60, 46, /* 18 */
3576 46, 46, 46, 46, 46, 46, 46, 46, /* 18 */
3577 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3578 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3579 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3580 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3581 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3582 23, 24, 23, 24, 23, 24, 23, 24, /* 18 */
3583 40, 23, 24, 23, 24, 46, 46, 23, /* 19 */
3584 24, 46, 46, 23, 24, 46, 46, 46, /* 19 */
3585 23, 24, 23, 24, 23, 24, 23, 24, /* 19 */
3586 23, 24, 23, 24, 23, 24, 23, 24, /* 19 */
3587 23, 24, 23, 24, 23, 24, 23, 24, /* 19 */
3588 23, 24, 23, 24, 46, 46, 23, 24, /* 19 */
3589 23, 24, 23, 24, 23, 24, 46, 46, /* 19 */
3590 23, 24, 46, 46, 46, 46, 46, 46, /* 19 */
3591 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3592 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3593 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3594 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3595 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3596 46, 46, 46, 46, 46, 46, 46, 46, /* 20 */
3597 46, 76, 76, 76, 76, 76, 76, 76, /* 20 */
3598 76, 76, 76, 76, 76, 76, 76, 76, /* 20 */
3599 76, 76, 76, 76, 76, 76, 76, 76, /* 21 */
3600 76, 76, 76, 76, 76, 76, 76, 76, /* 21 */
3601 76, 76, 76, 76, 76, 76, 76, 46, /* 21 */
3602 46, 59, 3, 3, 3, 3, 3, 3, /* 21 */
3603 46, 77, 77, 77, 77, 77, 77, 77, /* 21 */
3604 77, 77, 77, 77, 77, 77, 77, 77, /* 21 */
3605 77, 77, 77, 77, 77, 77, 77, 77, /* 21 */
3606 77, 77, 77, 77, 77, 77, 77, 77, /* 21 */
3607 77, 77, 77, 77, 77, 77, 77, 16, /* 22 */
3608 46, 3, 46, 46, 46, 46, 46, 46, /* 22 */
3609 46, 60, 60, 60, 60, 60, 60, 60, /* 22 */
3610 60, 60, 60, 60, 60, 60, 60, 60, /* 22 */
3611 60, 60, 46, 60, 60, 60, 60, 60, /* 22 */
3612 60, 60, 60, 60, 60, 60, 60, 60, /* 22 */
3613 60, 60, 60, 60, 60, 60, 60, 60, /* 22 */
3614 60, 60, 46, 60, 60, 60, 3, 60, /* 22 */
3615 3, 60, 60, 3, 60, 46, 46, 46, /* 23 */
3616 46, 46, 46, 46, 46, 46, 46, 46, /* 23 */
3617 40, 40, 40, 40, 40, 40, 40, 40, /* 23 */
3618 40, 40, 40, 40, 40, 40, 40, 40, /* 23 */
3619 40, 40, 40, 40, 40, 40, 40, 40, /* 23 */
3620 40, 40, 40, 46, 46, 46, 46, 46, /* 23 */
3621 40, 40, 40, 3, 3, 46, 46, 46, /* 23 */
3622 46, 46, 46, 46, 46, 46, 46, 46, /* 23 */
3623 46, 46, 46, 46, 46, 46, 46, 46, /* 24 */
3624 46, 46, 46, 46, 3, 46, 46, 46, /* 24 */
3625 46, 46, 46, 46, 46, 46, 46, 46, /* 24 */
3626 46, 46, 46, 3, 46, 46, 46, 3, /* 24 */
3627 46, 40, 40, 40, 40, 40, 40, 40, /* 24 */
3628 40, 40, 40, 40, 40, 40, 40, 40, /* 24 */
3629 40, 40, 40, 40, 40, 40, 40, 40, /* 24 */
3630 40, 40, 40, 46, 46, 46, 46, 46, /* 24 */
3631 59, 40, 40, 40, 40, 40, 40, 40, /* 25 */
3632 40, 40, 40, 60, 60, 60, 60, 60, /* 25 */
3633 60, 60, 60, 46, 46, 46, 46, 46, /* 25 */
3634 46, 46, 46, 46, 46, 46, 46, 46, /* 25 */
3635 78, 78, 78, 78, 78, 78, 78, 78, /* 25 */
3636 78, 78, 3, 3, 3, 3, 46, 46, /* 25 */
3637 60, 40, 40, 40, 40, 40, 40, 40, /* 25 */
3638 40, 40, 40, 40, 40, 40, 40, 40, /* 25 */
3639 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3640 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3641 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3642 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3643 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3644 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3645 40, 40, 40, 40, 40, 40, 40, 40, /* 26 */
3646 46, 46, 40, 40, 40, 40, 40, 46, /* 26 */
3647 40, 40, 40, 40, 40, 40, 40, 40, /* 27 */
3648 40, 40, 40, 40, 40, 40, 40, 46, /* 27 */
3649 40, 40, 40, 40, 3, 40, 60, 60, /* 27 */
3650 60, 60, 60, 60, 60, 79, 79, 60, /* 27 */
3651 60, 60, 60, 60, 60, 59, 59, 60, /* 27 */
3652 60, 15, 60, 60, 60, 60, 46, 46, /* 27 */
3653 9, 9, 9, 9, 9, 9, 9, 9, /* 27 */
3654 9, 9, 46, 46, 46, 46, 46, 46, /* 27 */
3655 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3656 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3657 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3658 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3659 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3660 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3661 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3662 46, 46, 46, 46, 46, 46, 46, 46, /* 28 */
3663 46, 60, 60, 80, 46, 40, 40, 40, /* 29 */
3664 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3665 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3666 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3667 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3668 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3669 40, 40, 40, 40, 40, 40, 40, 40, /* 29 */
3670 40, 40, 46, 46, 60, 40, 80, 80, /* 29 */
3671 80, 60, 60, 60, 60, 60, 60, 60, /* 30 */
3672 60, 80, 80, 80, 80, 60, 46, 46, /* 30 */
3673 15, 60, 60, 60, 60, 46, 46, 46, /* 30 */
3674 40, 40, 40, 40, 40, 40, 40, 40, /* 30 */
3675 40, 40, 60, 60, 3, 3, 81, 81, /* 30 */
3676 81, 81, 81, 81, 81, 81, 81, 81, /* 30 */
3677 3, 46, 46, 46, 46, 46, 46, 46, /* 30 */
3678 46, 46, 46, 46, 46, 46, 46, 46, /* 30 */
3679 46, 60, 80, 80, 46, 40, 40, 40, /* 31 */
3680 40, 40, 40, 40, 40, 46, 46, 40, /* 31 */
3681 40, 46, 46, 40, 40, 40, 40, 40, /* 31 */
3682 40, 40, 40, 40, 40, 40, 40, 40, /* 31 */
3683 40, 40, 40, 40, 40, 40, 40, 40, /* 31 */
3684 40, 46, 40, 40, 40, 40, 40, 40, /* 31 */
3685 40, 46, 40, 46, 46, 46, 40, 40, /* 31 */
3686 40, 40, 46, 46, 60, 46, 80, 80, /* 31 */
3687 80, 60, 60, 60, 60, 46, 46, 80, /* 32 */
3688 80, 46, 46, 80, 80, 60, 46, 46, /* 32 */
3689 46, 46, 46, 46, 46, 46, 46, 80, /* 32 */
3690 46, 46, 46, 46, 40, 40, 46, 40, /* 32 */
3691 40, 40, 60, 60, 46, 46, 81, 81, /* 32 */
3692 81, 81, 81, 81, 81, 81, 81, 81, /* 32 */
3693 40, 40, 4, 4, 82, 82, 82, 82, /* 32 */
3694 19, 83, 15, 46, 46, 46, 46, 46, /* 32 */
3695 46, 46, 60, 46, 46, 40, 40, 40, /* 33 */
3696 40, 40, 40, 46, 46, 46, 46, 40, /* 33 */
3697 40, 46, 46, 40, 40, 40, 40, 40, /* 33 */
3698 40, 40, 40, 40, 40, 40, 40, 40, /* 33 */
3699 40, 40, 40, 40, 40, 40, 40, 40, /* 33 */
3700 40, 46, 40, 40, 40, 40, 40, 40, /* 33 */
3701 40, 46, 40, 40, 46, 40, 40, 46, /* 33 */
3702 40, 40, 46, 46, 60, 46, 80, 80, /* 33 */
3703 80, 60, 60, 46, 46, 46, 46, 60, /* 34 */
3704 60, 46, 46, 60, 60, 60, 46, 46, /* 34 */
3705 46, 46, 46, 46, 46, 46, 46, 46, /* 34 */
3706 46, 40, 40, 40, 40, 46, 40, 46, /* 34 */
3707 46, 46, 46, 46, 46, 46, 81, 81, /* 34 */
3708 81, 81, 81, 81, 81, 81, 81, 81, /* 34 */
3709 60, 60, 40, 40, 40, 46, 46, 46, /* 34 */
3710 46, 46, 46, 46, 46, 46, 46, 46, /* 34 */
3711 46, 60, 60, 80, 46, 40, 40, 40, /* 35 */
3712 40, 40, 40, 40, 46, 40, 46, 40, /* 35 */
3713 40, 40, 46, 40, 40, 40, 40, 40, /* 35 */
3714 40, 40, 40, 40, 40, 40, 40, 40, /* 35 */
3715 40, 40, 40, 40, 40, 40, 40, 40, /* 35 */
3716 40, 46, 40, 40, 40, 40, 40, 40, /* 35 */
3717 40, 46, 40, 40, 46, 40, 40, 40, /* 35 */
3718 40, 40, 46, 46, 60, 40, 80, 80, /* 35 */
3719 80, 60, 60, 60, 60, 60, 46, 60, /* 36 */
3720 60, 80, 46, 80, 80, 60, 46, 46, /* 36 */
3721 15, 46, 46, 46, 46, 46, 46, 46, /* 36 */
3722 46, 46, 46, 46, 46, 46, 46, 46, /* 36 */
3723 40, 46, 46, 46, 46, 46, 81, 81, /* 36 */
3724 81, 81, 81, 81, 81, 81, 81, 81, /* 36 */
3725 46, 46, 46, 46, 46, 46, 46, 46, /* 36 */
3726 46, 46, 46, 46, 46, 46, 46, 46, /* 36 */
3727 46, 60, 80, 80, 46, 40, 40, 40, /* 37 */
3728 40, 40, 40, 40, 40, 46, 46, 40, /* 37 */
3729 40, 46, 46, 40, 40, 40, 40, 40, /* 37 */
3730 40, 40, 40, 40, 40, 40, 40, 40, /* 37 */
3731 40, 40, 40, 40, 40, 40, 40, 40, /* 37 */
3732 40, 46, 40, 40, 40, 40, 40, 40, /* 37 */
3733 40, 46, 40, 40, 46, 46, 40, 40, /* 37 */
3734 40, 40, 46, 46, 60, 40, 80, 60, /* 37 */
3735 80, 60, 60, 60, 46, 46, 46, 80, /* 38 */
3736 80, 46, 46, 80, 80, 60, 46, 46, /* 38 */
3737 46, 46, 46, 46, 46, 46, 60, 80, /* 38 */
3738 46, 46, 46, 46, 40, 40, 46, 40, /* 38 */
3739 40, 40, 46, 46, 46, 46, 81, 81, /* 38 */
3740 81, 81, 81, 81, 81, 81, 81, 81, /* 38 */
3741 15, 46, 46, 46, 46, 46, 46, 46, /* 38 */
3742 46, 46, 46, 46, 46, 46, 46, 46, /* 38 */
3743 46, 46, 60, 80, 46, 40, 40, 40, /* 39 */
3744 40, 40, 40, 46, 46, 46, 40, 40, /* 39 */
3745 40, 46, 40, 40, 40, 40, 46, 46, /* 39 */
3746 46, 40, 40, 46, 40, 46, 40, 40, /* 39 */
3747 46, 46, 46, 40, 40, 46, 46, 46, /* 39 */
3748 40, 40, 40, 46, 46, 46, 40, 40, /* 39 */
3749 40, 40, 40, 40, 40, 40, 46, 40, /* 39 */
3750 40, 40, 46, 46, 46, 46, 80, 80, /* 39 */
3751 60, 80, 80, 46, 46, 46, 80, 80, /* 40 */
3752 80, 46, 80, 80, 80, 60, 46, 46, /* 40 */
3753 46, 46, 46, 46, 46, 46, 46, 80, /* 40 */
3754 46, 46, 46, 46, 46, 46, 46, 46, /* 40 */
3755 46, 46, 46, 46, 46, 46, 46, 81, /* 40 */
3756 81, 81, 81, 81, 81, 81, 81, 81, /* 40 */
3757 84, 19, 19, 46, 46, 46, 46, 46, /* 40 */
3758 46, 46, 46, 46, 46, 46, 46, 46, /* 40 */
3759 46, 80, 80, 80, 46, 40, 40, 40, /* 41 */
3760 40, 40, 40, 40, 40, 46, 40, 40, /* 41 */
3761 40, 46, 40, 40, 40, 40, 40, 40, /* 41 */
3762 40, 40, 40, 40, 40, 40, 40, 40, /* 41 */
3763 40, 40, 40, 40, 40, 40, 40, 40, /* 41 */
3764 40, 46, 40, 40, 40, 40, 40, 40, /* 41 */
3765 40, 40, 40, 40, 46, 40, 40, 40, /* 41 */
3766 40, 40, 46, 46, 46, 46, 60, 60, /* 41 */
3767 60, 80, 80, 80, 80, 46, 60, 60, /* 42 */
3768 60, 46, 60, 60, 60, 60, 46, 46, /* 42 */
3769 46, 46, 46, 46, 46, 60, 60, 46, /* 42 */
3770 46, 46, 46, 46, 46, 46, 46, 46, /* 42 */
3771 40, 40, 46, 46, 46, 46, 81, 81, /* 42 */
3772 81, 81, 81, 81, 81, 81, 81, 81, /* 42 */
3773 46, 46, 46, 46, 46, 46, 46, 46, /* 42 */
3774 46, 46, 46, 46, 46, 46, 46, 46, /* 42 */
3775 46, 46, 80, 80, 46, 40, 40, 40, /* 43 */
3776 40, 40, 40, 40, 40, 46, 40, 40, /* 43 */
3777 40, 46, 40, 40, 40, 40, 40, 40, /* 43 */
3778 40, 40, 40, 40, 40, 40, 40, 40, /* 43 */
3779 40, 40, 40, 40, 40, 40, 40, 40, /* 43 */
3780 40, 46, 40, 40, 40, 40, 40, 40, /* 43 */
3781 40, 40, 40, 40, 46, 40, 40, 40, /* 43 */
3782 40, 40, 46, 46, 46, 46, 80, 60, /* 43 */
3783 80, 80, 80, 80, 80, 46, 60, 80, /* 44 */
3784 80, 46, 80, 80, 60, 60, 46, 46, /* 44 */
3785 46, 46, 46, 46, 46, 80, 80, 46, /* 44 */
3786 46, 46, 46, 46, 46, 46, 40, 46, /* 44 */
3787 40, 40, 46, 46, 46, 46, 81, 81, /* 44 */
3788 81, 81, 81, 81, 81, 81, 81, 81, /* 44 */
3789 46, 46, 46, 46, 46, 46, 46, 46, /* 44 */
3790 46, 46, 46, 46, 46, 46, 46, 46, /* 44 */
3791 46, 46, 80, 80, 46, 40, 40, 40, /* 45 */
3792 40, 40, 40, 40, 40, 46, 40, 40, /* 45 */
3793 40, 46, 40, 40, 40, 40, 40, 40, /* 45 */
3794 40, 40, 40, 40, 40, 40, 40, 40, /* 45 */
3795 40, 40, 40, 40, 40, 40, 40, 40, /* 45 */
3796 40, 46, 40, 40, 40, 40, 40, 40, /* 45 */
3797 40, 40, 40, 40, 40, 40, 40, 40, /* 45 */
3798 40, 40, 46, 46, 46, 46, 80, 80, /* 45 */
3799 80, 60, 60, 60, 46, 46, 80, 80, /* 46 */
3800 80, 46, 80, 80, 80, 60, 46, 46, /* 46 */
3801 46, 46, 46, 46, 46, 46, 46, 80, /* 46 */
3802 46, 46, 46, 46, 46, 46, 46, 46, /* 46 */
3803 40, 40, 46, 46, 46, 46, 81, 81, /* 46 */
3804 81, 81, 81, 81, 81, 81, 81, 81, /* 46 */
3805 46, 46, 46, 46, 46, 46, 46, 46, /* 46 */
3806 46, 46, 46, 46, 46, 46, 46, 46, /* 46 */
3807 46, 40, 40, 40, 40, 40, 40, 40, /* 47 */
3808 40, 40, 40, 40, 40, 40, 40, 40, /* 47 */
3809 40, 40, 40, 40, 40, 40, 40, 40, /* 47 */
3810 40, 40, 40, 40, 40, 40, 40, 40, /* 47 */
3811 40, 40, 40, 40, 40, 40, 40, 40, /* 47 */
3812 40, 40, 40, 40, 40, 40, 40, 3, /* 47 */
3813 40, 60, 40, 40, 60, 60, 60, 60, /* 47 */
3814 60, 60, 60, 46, 46, 46, 46, 4, /* 47 */
3815 40, 40, 40, 40, 40, 40, 59, 60, /* 48 */
3816 60, 60, 60, 60, 60, 60, 60, 15, /* 48 */
3817 9, 9, 9, 9, 9, 9, 9, 9, /* 48 */
3818 9, 9, 3, 3, 46, 46, 46, 46, /* 48 */
3819 46, 46, 46, 46, 46, 46, 46, 46, /* 48 */
3820 46, 46, 46, 46, 46, 46, 46, 46, /* 48 */
3821 46, 46, 46, 46, 46, 46, 46, 46, /* 48 */
3822 46, 46, 46, 46, 46, 46, 46, 46, /* 48 */
3823 46, 40, 40, 46, 40, 46, 46, 40, /* 49 */
3824 40, 46, 40, 46, 46, 40, 46, 46, /* 49 */
3825 46, 46, 46, 46, 40, 40, 40, 40, /* 49 */
3826 46, 40, 40, 40, 40, 40, 40, 40, /* 49 */
3827 46, 40, 40, 40, 46, 40, 46, 40, /* 49 */
3828 46, 46, 40, 40, 46, 40, 40, 3, /* 49 */
3829 40, 60, 40, 40, 60, 60, 60, 60, /* 49 */
3830 60, 60, 46, 60, 60, 40, 46, 46, /* 49 */
3831 40, 40, 40, 40, 40, 46, 59, 46, /* 50 */
3832 60, 60, 60, 60, 60, 60, 46, 46, /* 50 */
3833 9, 9, 9, 9, 9, 9, 9, 9, /* 50 */
3834 9, 9, 46, 46, 40, 40, 46, 46, /* 50 */
3835 46, 46, 46, 46, 46, 46, 46, 46, /* 50 */
3836 46, 46, 46, 46, 46, 46, 46, 46, /* 50 */
3837 46, 46, 46, 46, 46, 46, 46, 46, /* 50 */
3838 46, 46, 46, 46, 46, 46, 46, 46, /* 50 */
3839 15, 15, 15, 15, 3, 3, 3, 3, /* 51 */
3840 3, 3, 3, 3, 3, 3, 3, 3, /* 51 */
3841 3, 3, 3, 15, 15, 15, 15, 15, /* 51 */
3842 60, 60, 15, 15, 15, 15, 15, 15, /* 51 */
3843 78, 78, 78, 78, 78, 78, 78, 78, /* 51 */
3844 78, 78, 85, 85, 85, 85, 85, 85, /* 51 */
3845 85, 85, 85, 85, 15, 60, 15, 60, /* 51 */
3846 15, 60, 5, 6, 5, 6, 80, 80, /* 51 */
3847 40, 40, 40, 40, 40, 40, 40, 40, /* 52 */
3848 46, 40, 40, 40, 40, 40, 40, 40, /* 52 */
3849 40, 40, 40, 40, 40, 40, 40, 40, /* 52 */
3850 40, 40, 40, 40, 40, 40, 40, 40, /* 52 */
3851 40, 40, 40, 40, 40, 40, 40, 40, /* 52 */
3852 40, 40, 46, 46, 46, 46, 46, 46, /* 52 */
3853 46, 60, 60, 60, 60, 60, 60, 60, /* 52 */
3854 60, 60, 60, 60, 60, 60, 60, 80, /* 52 */
3855 60, 60, 60, 60, 60, 3, 60, 60, /* 53 */
3856 60, 60, 60, 60, 46, 46, 46, 46, /* 53 */
3857 60, 60, 60, 60, 60, 60, 46, 60, /* 53 */
3858 46, 60, 60, 60, 60, 60, 60, 60, /* 53 */
3859 60, 60, 60, 60, 60, 60, 60, 60, /* 53 */
3860 60, 60, 60, 60, 60, 60, 46, 46, /* 53 */
3861 46, 60, 60, 60, 60, 60, 60, 60, /* 53 */
3862 46, 60, 46, 46, 46, 46, 46, 46, /* 53 */
3863 46, 46, 46, 46, 46, 46, 46, 46, /* 54 */
3864 46, 46, 46, 46, 46, 46, 46, 46, /* 54 */
3865 46, 46, 46, 46, 46, 46, 46, 46, /* 54 */
3866 46, 46, 46, 46, 46, 46, 46, 46, /* 54 */
3867 76, 76, 76, 76, 76, 76, 76, 76, /* 54 */
3868 76, 76, 76, 76, 76, 76, 76, 76, /* 54 */
3869 76, 76, 76, 76, 76, 76, 76, 76, /* 54 */
3870 76, 76, 76, 76, 76, 76, 76, 76, /* 54 */
3871 76, 76, 76, 76, 76, 76, 46, 46, /* 55 */
3872 46, 46, 46, 46, 46, 46, 46, 46, /* 55 */
3873 16, 16, 16, 16, 16, 16, 16, 16, /* 55 */
3874 16, 16, 16, 16, 16, 16, 16, 16, /* 55 */
3875 16, 16, 16, 16, 16, 16, 16, 16, /* 55 */
3876 16, 16, 16, 16, 16, 16, 16, 16, /* 55 */
3877 16, 16, 16, 16, 16, 16, 16, 46, /* 55 */
3878 46, 46, 46, 3, 46, 46, 46, 46, /* 55 */
3879 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3880 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3881 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3882 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3883 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3884 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3885 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3886 40, 40, 40, 40, 40, 40, 40, 40, /* 56 */
3887 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3888 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3889 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3890 40, 40, 46, 46, 46, 46, 46, 40, /* 57 */
3891 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3892 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3893 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3894 40, 40, 40, 40, 40, 40, 40, 40, /* 57 */
3895 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3896 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3897 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3898 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3899 40, 40, 40, 46, 46, 46, 46, 46, /* 58 */
3900 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3901 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3902 40, 40, 40, 40, 40, 40, 40, 40, /* 58 */
3903 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3904 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3905 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3906 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3907 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3908 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3909 40, 40, 40, 40, 40, 40, 40, 40, /* 59 */
3910 40, 40, 46, 46, 46, 46, 46, 46, /* 59 */
3911 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3912 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3913 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3914 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3915 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3916 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3917 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3918 23, 24, 23, 24, 23, 24, 23, 24, /* 60 */
3919 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3920 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3921 23, 24, 23, 24, 23, 24, 16, 16, /* 61 */
3922 16, 16, 16, 16, 46, 46, 46, 46, /* 61 */
3923 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3924 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3925 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3926 23, 24, 23, 24, 23, 24, 23, 24, /* 61 */
3927 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3928 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3929 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3930 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3931 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3932 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3933 23, 24, 23, 24, 23, 24, 23, 24, /* 62 */
3934 23, 24, 46, 46, 46, 46, 46, 46, /* 62 */
3935 86, 86, 86, 86, 86, 86, 86, 86, /* 63 */
3936 87, 87, 87, 87, 87, 87, 87, 87, /* 63 */
3937 86, 86, 86, 86, 86, 86, 46, 46, /* 63 */
3938 87, 87, 87, 87, 87, 87, 46, 46, /* 63 */
3939 86, 86, 86, 86, 86, 86, 86, 86, /* 63 */
3940 87, 87, 87, 87, 87, 87, 87, 87, /* 63 */
3941 86, 86, 86, 86, 86, 86, 86, 86, /* 63 */
3942 87, 87, 87, 87, 87, 87, 87, 87, /* 63 */
3943 86, 86, 86, 86, 86, 86, 46, 46, /* 64 */
3944 87, 87, 87, 87, 87, 87, 46, 46, /* 64 */
3945 16, 86, 16, 86, 16, 86, 16, 86, /* 64 */
3946 46, 87, 46, 87, 46, 87, 46, 87, /* 64 */
3947 86, 86, 86, 86, 86, 86, 86, 86, /* 64 */
3948 87, 87, 87, 87, 87, 87, 87, 87, /* 64 */
3949 88, 88, 89, 89, 89, 89, 90, 90, /* 64 */
3950 91, 91, 92, 92, 93, 93, 46, 46, /* 64 */
3951 86, 86, 86, 86, 86, 86, 86, 86, /* 65 */
3952 87, 87, 87, 87, 87, 87, 87, 87, /* 65 */
3953 86, 86, 86, 86, 86, 86, 86, 86, /* 65 */
3954 87, 87, 87, 87, 87, 87, 87, 87, /* 65 */
3955 86, 86, 86, 86, 86, 86, 86, 86, /* 65 */
3956 87, 87, 87, 87, 87, 87, 87, 87, /* 65 */
3957 86, 86, 16, 94, 16, 46, 16, 16, /* 65 */
3958 87, 87, 95, 95, 96, 11, 38, 11, /* 65 */
3959 11, 11, 16, 94, 16, 46, 16, 16, /* 66 */
3960 97, 97, 97, 97, 96, 11, 11, 11, /* 66 */
3961 86, 86, 16, 16, 46, 46, 16, 16, /* 66 */
3962 87, 87, 98, 98, 46, 11, 11, 11, /* 66 */
3963 86, 86, 16, 16, 16, 99, 16, 16, /* 66 */
3964 87, 87, 100, 100, 101, 11, 11, 11, /* 66 */
3965 46, 46, 16, 94, 16, 46, 16, 16, /* 66 */
3966 102, 102, 103, 103, 96, 11, 11, 46, /* 66 */
3967 2, 2, 2, 2, 2, 2, 2, 2, /* 67 */
3968 2, 2, 2, 2, 104, 104, 104, 104, /* 67 */
3969 8, 8, 8, 8, 8, 8, 3, 3, /* 67 */
3970 5, 6, 5, 5, 5, 6, 5, 5, /* 67 */
3971 3, 3, 3, 3, 3, 3, 3, 3, /* 67 */
3972 105, 106, 104, 104, 104, 104, 104, 46, /* 67 */
3973 3, 3, 3, 3, 3, 3, 3, 3, /* 67 */
3974 3, 5, 6, 3, 3, 3, 3, 12, /* 67 */
3975 12, 3, 3, 3, 7, 5, 6, 46, /* 68 */
3976 46, 46, 46, 46, 46, 46, 46, 46, /* 68 */
3977 46, 46, 46, 46, 46, 46, 46, 46, /* 68 */
3978 46, 46, 46, 46, 46, 46, 46, 46, /* 68 */
3979 46, 46, 46, 46, 46, 46, 46, 46, /* 68 */
3980 46, 46, 104, 104, 104, 104, 104, 104, /* 68 */
3981 17, 46, 46, 46, 17, 17, 17, 17, /* 68 */
3982 17, 17, 7, 7, 7, 5, 6, 16, /* 68 */
3983 107, 107, 107, 107, 107, 107, 107, 107, /* 69 */
3984 107, 107, 7, 7, 7, 5, 6, 46, /* 69 */
3985 46, 46, 46, 46, 46, 46, 46, 46, /* 69 */
3986 46, 46, 46, 46, 46, 46, 46, 46, /* 69 */
3987 4, 4, 4, 4, 4, 4, 4, 4, /* 69 */
3988 4, 4, 4, 4, 46, 46, 46, 46, /* 69 */
3989 46, 46, 46, 46, 46, 46, 46, 46, /* 69 */
3990 46, 46, 46, 46, 46, 46, 46, 46, /* 69 */
3991 46, 46, 46, 46, 46, 46, 46, 46, /* 70 */
3992 46, 46, 46, 46, 46, 46, 46, 46, /* 70 */
3993 60, 60, 60, 60, 60, 60, 60, 60, /* 70 */
3994 60, 60, 60, 60, 60, 79, 79, 79, /* 70 */
3995 79, 60, 46, 46, 46, 46, 46, 46, /* 70 */
3996 46, 46, 46, 46, 46, 46, 46, 46, /* 70 */
3997 46, 46, 46, 46, 46, 46, 46, 46, /* 70 */
3998 46, 46, 46, 46, 46, 46, 46, 46, /* 70 */
3999 15, 15, 38, 15, 15, 15, 15, 38, /* 71 */
4000 15, 15, 16, 38, 38, 38, 16, 16, /* 71 */
4001 38, 38, 38, 16, 15, 38, 15, 15, /* 71 */
4002 38, 38, 38, 38, 38, 38, 15, 15, /* 71 */
4003 15, 15, 15, 15, 38, 15, 38, 15, /* 71 */
4004 38, 15, 38, 38, 38, 38, 16, 16, /* 71 */
4005 38, 38, 15, 38, 16, 40, 40, 40, /* 71 */
4006 40, 46, 46, 46, 46, 46, 46, 46, /* 71 */
4007 46, 46, 46, 46, 46, 46, 46, 46, /* 72 */
4008 46, 46, 46, 46, 46, 46, 46, 46, /* 72 */
4009 46, 46, 46, 19, 19, 19, 19, 19, /* 72 */
4010 19, 19, 19, 19, 19, 19, 19, 108, /* 72 */
4011 109, 109, 109, 109, 109, 109, 109, 109, /* 72 */
4012 109, 109, 109, 109, 110, 110, 110, 110, /* 72 */
4013 111, 111, 111, 111, 111, 111, 111, 111, /* 72 */
4014 111, 111, 111, 111, 112, 112, 112, 112, /* 72 */
4015 113, 113, 113, 46, 46, 46, 46, 46, /* 73 */
4016 46, 46, 46, 46, 46, 46, 46, 46, /* 73 */
4017 7, 7, 7, 7, 7, 15, 15, 15, /* 73 */
4018 15, 15, 15, 15, 15, 15, 15, 15, /* 73 */
4019 15, 15, 15, 15, 15, 15, 15, 15, /* 73 */
4020 15, 15, 15, 15, 15, 15, 15, 15, /* 73 */
4021 15, 15, 15, 15, 15, 15, 15, 15, /* 73 */
4022 15, 15, 15, 15, 15, 15, 15, 15, /* 73 */
4023 15, 15, 15, 15, 15, 15, 15, 15, /* 74 */
4024 15, 15, 15, 15, 15, 15, 15, 15, /* 74 */
4025 15, 15, 7, 15, 7, 15, 15, 15, /* 74 */
4026 15, 15, 15, 15, 15, 15, 15, 15, /* 74 */
4027 15, 15, 15, 15, 15, 15, 15, 15, /* 74 */
4028 15, 15, 15, 46, 46, 46, 46, 46, /* 74 */
4029 46, 46, 46, 46, 46, 46, 46, 46, /* 74 */
4030 46, 46, 46, 46, 46, 46, 46, 46, /* 74 */
4031 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4032 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4033 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4034 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4035 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4036 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4037 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4038 7, 7, 7, 7, 7, 7, 7, 7, /* 75 */
4039 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4040 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4041 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4042 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4043 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4044 7, 7, 7, 7, 7, 7, 7, 7, /* 76 */
4045 7, 7, 46, 46, 46, 46, 46, 46, /* 76 */
4046 46, 46, 46, 46, 46, 46, 46, 46, /* 76 */
4047 15, 46, 15, 15, 15, 15, 15, 15, /* 77 */
4048 7, 7, 7, 7, 15, 15, 15, 15, /* 77 */
4049 15, 15, 15, 15, 15, 15, 15, 15, /* 77 */
4050 15, 15, 15, 15, 15, 15, 15, 15, /* 77 */
4051 7, 7, 15, 15, 15, 15, 15, 15, /* 77 */
4052 15, 5, 6, 15, 15, 15, 15, 15, /* 77 */
4053 15, 15, 15, 15, 15, 15, 15, 15, /* 77 */
4054 15, 15, 15, 15, 15, 15, 15, 15, /* 77 */
4055 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4056 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4057 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4058 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4059 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4060 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4061 15, 15, 15, 15, 15, 15, 15, 15, /* 78 */
4062 15, 15, 15, 46, 46, 46, 46, 46, /* 78 */
4063 15, 15, 15, 15, 15, 15, 15, 15, /* 79 */
4064 15, 15, 15, 15, 15, 15, 15, 15, /* 79 */
4065 15, 15, 15, 15, 15, 15, 15, 15, /* 79 */
4066 15, 15, 15, 15, 15, 15, 15, 15, /* 79 */
4067 15, 15, 15, 15, 15, 46, 46, 46, /* 79 */
4068 46, 46, 46, 46, 46, 46, 46, 46, /* 79 */
4069 46, 46, 46, 46, 46, 46, 46, 46, /* 79 */
4070 46, 46, 46, 46, 46, 46, 46, 46, /* 79 */
4071 15, 15, 15, 15, 15, 15, 15, 15, /* 80 */
4072 15, 15, 15, 46, 46, 46, 46, 46, /* 80 */
4073 46, 46, 46, 46, 46, 46, 46, 46, /* 80 */
4074 46, 46, 46, 46, 46, 46, 46, 46, /* 80 */
4075 114, 114, 114, 114, 114, 114, 114, 114, /* 80 */
4076 114, 114, 114, 114, 114, 114, 114, 114, /* 80 */
4077 114, 114, 114, 114, 82, 82, 82, 82, /* 80 */
4078 82, 82, 82, 82, 82, 82, 82, 82, /* 80 */
4079 82, 82, 82, 82, 82, 82, 82, 82, /* 81 */
4080 115, 115, 115, 115, 115, 115, 115, 115, /* 81 */
4081 115, 115, 115, 115, 115, 115, 115, 115, /* 81 */
4082 115, 115, 115, 115, 15, 15, 15, 15, /* 81 */
4083 15, 15, 15, 15, 15, 15, 15, 15, /* 81 */
4084 15, 15, 15, 15, 15, 15, 15, 15, /* 81 */
4085 15, 15, 15, 15, 15, 15, 116, 116, /* 81 */
4086 116, 116, 116, 116, 116, 116, 116, 116, /* 81 */
4087 116, 116, 116, 116, 116, 116, 116, 116, /* 82 */
4088 116, 116, 116, 116, 116, 116, 116, 116, /* 82 */
4089 117, 117, 117, 117, 117, 117, 117, 117, /* 82 */
4090 117, 117, 117, 117, 117, 117, 117, 117, /* 82 */
4091 117, 117, 117, 117, 117, 117, 117, 117, /* 82 */
4092 117, 117, 118, 46, 46, 46, 46, 46, /* 82 */
4093 46, 46, 46, 46, 46, 46, 46, 46, /* 82 */
4094 46, 46, 46, 46, 46, 46, 46, 46, /* 82 */
4095 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4096 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4097 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4098 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4099 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4100 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4101 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4102 15, 15, 15, 15, 15, 15, 15, 15, /* 83 */
4103 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4104 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4105 15, 15, 15, 15, 15, 15, 46, 46, /* 84 */
4106 46, 46, 46, 46, 46, 46, 46, 46, /* 84 */
4107 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4108 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4109 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4110 15, 15, 15, 15, 15, 15, 15, 15, /* 84 */
4111 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4112 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4113 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4114 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4115 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4116 15, 15, 15, 15, 15, 15, 15, 15, /* 85 */
4117 46, 46, 46, 46, 46, 46, 46, 46, /* 85 */
4118 46, 46, 46, 46, 46, 46, 46, 46, /* 85 */
4119 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4120 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4121 15, 15, 15, 15, 46, 46, 46, 46, /* 86 */
4122 46, 46, 15, 15, 15, 15, 15, 15, /* 86 */
4123 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4124 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4125 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4126 15, 15, 15, 15, 15, 15, 15, 15, /* 86 */
4127 46, 15, 15, 15, 15, 46, 15, 15, /* 87 */
4128 15, 15, 46, 46, 15, 15, 15, 15, /* 87 */
4129 15, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4130 15, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4131 15, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4132 46, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4133 15, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4134 15, 15, 15, 15, 15, 15, 15, 15, /* 87 */
4135 15, 15, 15, 15, 15, 15, 15, 15, /* 88 */
4136 15, 15, 15, 15, 46, 15, 46, 15, /* 88 */
4137 15, 15, 15, 46, 46, 46, 15, 46, /* 88 */
4138 15, 15, 15, 15, 15, 15, 15, 46, /* 88 */
4139 46, 15, 15, 15, 15, 15, 15, 15, /* 88 */
4140 46, 46, 46, 46, 46, 46, 46, 46, /* 88 */
4141 46, 46, 46, 46, 46, 46, 119, 119, /* 88 */
4142 119, 119, 119, 119, 119, 119, 119, 119, /* 88 */
4143 114, 114, 114, 114, 114, 114, 114, 114, /* 89 */
4144 114, 114, 83, 83, 83, 83, 83, 83, /* 89 */
4145 83, 83, 83, 83, 15, 46, 46, 46, /* 89 */
4146 15, 15, 15, 15, 15, 15, 15, 15, /* 89 */
4147 15, 15, 15, 15, 15, 15, 15, 15, /* 89 */
4148 15, 15, 15, 15, 15, 15, 15, 15, /* 89 */
4149 46, 15, 15, 15, 15, 15, 15, 15, /* 89 */
4150 15, 15, 15, 15, 15, 15, 15, 46, /* 89 */
4151 2, 3, 3, 3, 15, 59, 3, 120, /* 90 */
4152 5, 6, 5, 6, 5, 6, 5, 6, /* 90 */
4153 5, 6, 15, 15, 5, 6, 5, 6, /* 90 */
4154 5, 6, 5, 6, 8, 5, 6, 5, /* 90 */
4155 15, 121, 121, 121, 121, 121, 121, 121, /* 90 */
4156 121, 121, 60, 60, 60, 60, 60, 60, /* 90 */
4157 8, 59, 59, 59, 59, 59, 15, 15, /* 90 */
4158 46, 46, 46, 46, 46, 46, 46, 15, /* 90 */
4159 46, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4160 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4161 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4162 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4163 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4164 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4165 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4166 40, 40, 40, 40, 40, 40, 40, 40, /* 91 */
4167 40, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4168 40, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4169 40, 40, 40, 40, 40, 46, 46, 46, /* 92 */
4170 46, 60, 60, 59, 59, 59, 59, 46, /* 92 */
4171 46, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4172 40, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4173 40, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4174 40, 40, 40, 40, 40, 40, 40, 40, /* 92 */
4175 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4176 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4177 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4178 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4179 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4180 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4181 40, 40, 40, 40, 40, 40, 40, 40, /* 93 */
4182 40, 40, 40, 3, 59, 59, 59, 46, /* 93 */
4183 46, 46, 46, 46, 46, 40, 40, 40, /* 94 */
4184 40, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4185 40, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4186 40, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4187 40, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4188 40, 40, 40, 40, 40, 46, 46, 46, /* 94 */
4189 46, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4190 40, 40, 40, 40, 40, 40, 40, 40, /* 94 */
4191 40, 40, 40, 40, 40, 40, 40, 40, /* 95 */
4192 40, 40, 40, 40, 40, 40, 40, 46, /* 95 */
4193 15, 15, 85, 85, 85, 85, 15, 15, /* 95 */
4194 15, 15, 15, 15, 15, 15, 15, 15, /* 95 */
4195 46, 46, 46, 46, 46, 46, 46, 46, /* 95 */
4196 46, 46, 46, 46, 46, 46, 46, 46, /* 95 */
4197 46, 46, 46, 46, 46, 46, 46, 46, /* 95 */
4198 46, 46, 46, 46, 46, 46, 46, 46, /* 95 */
4199 15, 15, 15, 15, 15, 15, 15, 15, /* 96 */
4200 15, 15, 15, 15, 15, 15, 15, 15, /* 96 */
4201 15, 15, 15, 15, 15, 15, 15, 15, /* 96 */
4202 15, 15, 15, 15, 15, 46, 46, 46, /* 96 */
4203 85, 85, 85, 85, 85, 85, 85, 85, /* 96 */
4204 85, 85, 15, 15, 15, 15, 15, 15, /* 96 */
4205 15, 15, 15, 15, 15, 15, 15, 15, /* 96 */
4206 15, 15, 15, 15, 15, 15, 15, 15, /* 96 */
4207 15, 15, 15, 15, 46, 46, 46, 46, /* 97 */
4208 46, 46, 46, 46, 46, 46, 46, 46, /* 97 */
4209 46, 46, 46, 46, 46, 46, 46, 46, /* 97 */
4210 46, 46, 46, 46, 46, 46, 46, 46, /* 97 */
4211 15, 15, 15, 15, 15, 15, 15, 15, /* 97 */
4212 15, 15, 15, 15, 15, 15, 15, 15, /* 97 */
4213 15, 15, 15, 15, 15, 15, 15, 15, /* 97 */
4214 15, 15, 15, 15, 46, 46, 46, 15, /* 97 */
4215 114, 114, 114, 114, 114, 114, 114, 114, /* 98 */
4216 114, 114, 15, 15, 15, 15, 15, 15, /* 98 */
4217 15, 15, 15, 15, 15, 15, 15, 15, /* 98 */
4218 15, 15, 15, 15, 15, 15, 15, 15, /* 98 */
4219 15, 15, 15, 15, 15, 15, 15, 15, /* 98 */
4220 15, 15, 15, 15, 15, 15, 15, 15, /* 98 */
4221 15, 46, 46, 46, 46, 46, 46, 46, /* 98 */
4222 46, 46, 46, 46, 46, 46, 46, 46, /* 98 */
4223 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4224 15, 15, 15, 15, 46, 46, 46, 46, /* 99 */
4225 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4226 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4227 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4228 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4229 15, 15, 15, 15, 15, 15, 15, 15, /* 99 */
4230 15, 15, 15, 15, 15, 15, 15, 46, /* 99 */
4231 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4232 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4233 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4234 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4235 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4236 15, 15, 15, 15, 15, 15, 15, 15, /* 100 */
4237 15, 15, 15, 15, 15, 15, 15, 46, /* 100 */
4238 46, 46, 46, 15, 15, 15, 15, 15, /* 100 */
4239 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4240 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4241 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4242 15, 15, 15, 15, 15, 15, 46, 46, /* 101 */
4243 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4244 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4245 15, 15, 15, 15, 15, 15, 15, 15, /* 101 */
4246 15, 15, 15, 15, 15, 15, 15, 46, /* 101 */
4247 40, 40, 40, 40, 40, 40, 40, 40, /* 102 */
4248 40, 40, 40, 40, 40, 40, 40, 40, /* 102 */
4249 40, 40, 40, 40, 40, 40, 40, 40, /* 102 */
4250 40, 40, 40, 40, 40, 40, 40, 40, /* 102 */
4251 40, 40, 40, 40, 40, 40, 46, 46, /* 102 */
4252 46, 46, 46, 46, 46, 46, 46, 46, /* 102 */
4253 46, 46, 46, 46, 46, 46, 46, 46, /* 102 */
4254 46, 46, 46, 46, 46, 46, 46, 46, /* 102 */
4255 40, 40, 40, 40, 40, 40, 40, 40, /* 103 */
4256 40, 40, 40, 40, 40, 40, 40, 40, /* 103 */
4257 40, 40, 40, 40, 40, 40, 40, 40, /* 103 */
4258 40, 40, 40, 40, 40, 40, 40, 40, /* 103 */
4259 40, 40, 40, 40, 46, 46, 46, 46, /* 103 */
4260 46, 46, 46, 46, 46, 46, 46, 46, /* 103 */
4261 46, 46, 46, 46, 46, 46, 46, 46, /* 103 */
4262 46, 46, 46, 46, 46, 46, 46, 46, /* 103 */
4263 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4264 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4265 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4266 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4267 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4268 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4269 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4270 122, 122, 122, 122, 122, 122, 122, 122, /* 104 */
4271 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4272 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4273 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4274 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4275 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4276 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4277 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4278 123, 123, 123, 123, 123, 123, 123, 123, /* 105 */
4279 40, 40, 40, 40, 40, 40, 40, 40, /* 106 */
4280 40, 40, 40, 40, 40, 40, 40, 40, /* 106 */
4281 40, 40, 40, 40, 40, 40, 40, 40, /* 106 */
4282 40, 40, 40, 40, 40, 40, 40, 40, /* 106 */
4283 40, 40, 40, 40, 40, 40, 40, 40, /* 106 */
4284 40, 40, 40, 40, 40, 40, 46, 46, /* 106 */
4285 46, 46, 46, 46, 46, 46, 46, 46, /* 106 */
4286 46, 46, 46, 46, 46, 46, 46, 46, /* 106 */
4287 16, 16, 16, 16, 16, 16, 16, 46, /* 107 */
4288 46, 46, 46, 46, 46, 46, 46, 46, /* 107 */
4289 46, 46, 46, 16, 16, 16, 16, 16, /* 107 */
4290 46, 46, 46, 46, 46, 46, 60, 40, /* 107 */
4291 40, 40, 40, 40, 40, 40, 40, 40, /* 107 */
4292 40, 7, 40, 40, 40, 40, 40, 40, /* 107 */
4293 40, 40, 40, 40, 40, 40, 40, 46, /* 107 */
4294 40, 40, 40, 40, 40, 46, 40, 46, /* 107 */
4295 40, 40, 46, 40, 40, 46, 40, 40, /* 108 */
4296 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4297 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4298 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4299 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4300 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4301 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4302 40, 40, 40, 40, 40, 40, 40, 40, /* 108 */
4303 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4304 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4305 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4306 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4307 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4308 40, 40, 40, 40, 40, 40, 40, 40, /* 109 */
4309 40, 40, 46, 46, 46, 46, 46, 46, /* 109 */
4310 46, 46, 46, 46, 46, 46, 46, 46, /* 109 */
4311 46, 46, 46, 46, 46, 46, 46, 46, /* 110 */
4312 46, 46, 46, 46, 46, 46, 46, 46, /* 110 */
4313 46, 46, 46, 40, 40, 40, 40, 40, /* 110 */
4314 40, 40, 40, 40, 40, 40, 40, 40, /* 110 */
4315 40, 40, 40, 40, 40, 40, 40, 40, /* 110 */
4316 40, 40, 40, 40, 40, 40, 40, 40, /* 110 */
4317 40, 40, 40, 40, 40, 40, 40, 40, /* 110 */
4318 40, 40, 40, 40, 40, 40, 40, 40, /* 110 */
4319 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4320 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4321 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4322 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4323 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4324 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4325 40, 40, 40, 40, 40, 40, 40, 40, /* 111 */
4326 40, 40, 40, 40, 40, 40, 5, 6, /* 111 */
4327 46, 46, 46, 46, 46, 46, 46, 46, /* 112 */
4328 46, 46, 46, 46, 46, 46, 46, 46, /* 112 */
4329 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4330 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4331 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4332 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4333 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4334 40, 40, 40, 40, 40, 40, 40, 40, /* 112 */
4335 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4336 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4337 46, 46, 40, 40, 40, 40, 40, 40, /* 113 */
4338 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4339 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4340 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4341 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4342 40, 40, 40, 40, 40, 40, 40, 40, /* 113 */
4343 40, 40, 40, 40, 40, 40, 40, 40, /* 114 */
4344 46, 46, 46, 46, 46, 46, 46, 46, /* 114 */
4345 46, 46, 46, 46, 46, 46, 46, 46, /* 114 */
4346 46, 46, 46, 46, 46, 46, 46, 46, /* 114 */
4347 46, 46, 46, 46, 46, 46, 46, 46, /* 114 */
4348 46, 46, 46, 46, 46, 46, 46, 46, /* 114 */
4349 40, 40, 40, 40, 40, 40, 40, 40, /* 114 */
4350 40, 40, 40, 40, 46, 46, 46, 46, /* 114 */
4351 46, 46, 46, 46, 46, 46, 46, 46, /* 115 */
4352 46, 46, 46, 46, 46, 46, 46, 46, /* 115 */
4353 46, 46, 46, 46, 46, 46, 46, 46, /* 115 */
4354 46, 46, 46, 46, 46, 46, 46, 46, /* 115 */
4355 60, 60, 60, 60, 46, 46, 46, 46, /* 115 */
4356 46, 46, 46, 46, 46, 46, 46, 46, /* 115 */
4357 3, 8, 8, 12, 12, 5, 6, 5, /* 115 */
4358 6, 5, 6, 5, 6, 5, 6, 5, /* 115 */
4359 6, 5, 6, 5, 6, 46, 46, 46, /* 116 */
4360 46, 3, 3, 3, 3, 12, 12, 12, /* 116 */
4361 3, 3, 3, 46, 3, 3, 3, 3, /* 116 */
4362 8, 5, 6, 5, 6, 5, 6, 3, /* 116 */
4363 3, 3, 7, 8, 7, 7, 7, 46, /* 116 */
4364 3, 4, 3, 3, 46, 46, 46, 46, /* 116 */
4365 40, 40, 40, 46, 40, 46, 40, 40, /* 116 */
4366 40, 40, 40, 40, 40, 40, 40, 40, /* 116 */
4367 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4368 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4369 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4370 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4371 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4372 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4373 40, 40, 40, 40, 40, 40, 40, 40, /* 117 */
4374 40, 40, 40, 40, 40, 46, 46, 104, /* 117 */
4375 46, 3, 3, 3, 4, 3, 3, 3, /* 118 */
4376 5, 6, 3, 7, 3, 8, 3, 3, /* 118 */
4377 9, 9, 9, 9, 9, 9, 9, 9, /* 118 */
4378 9, 9, 3, 3, 7, 7, 7, 3, /* 118 */
4379 3, 10, 10, 10, 10, 10, 10, 10, /* 118 */
4380 10, 10, 10, 10, 10, 10, 10, 10, /* 118 */
4381 10, 10, 10, 10, 10, 10, 10, 10, /* 118 */
4382 10, 10, 10, 5, 3, 6, 11, 12, /* 118 */
4383 11, 13, 13, 13, 13, 13, 13, 13, /* 119 */
4384 13, 13, 13, 13, 13, 13, 13, 13, /* 119 */
4385 13, 13, 13, 13, 13, 13, 13, 13, /* 119 */
4386 13, 13, 13, 5, 7, 6, 7, 46, /* 119 */
4387 46, 3, 5, 6, 3, 3, 40, 40, /* 119 */
4388 40, 40, 40, 40, 40, 40, 40, 40, /* 119 */
4389 59, 40, 40, 40, 40, 40, 40, 40, /* 119 */
4390 40, 40, 40, 40, 40, 40, 40, 40, /* 119 */
4391 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4392 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4393 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4394 40, 40, 40, 40, 40, 40, 59, 59, /* 120 */
4395 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4396 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4397 40, 40, 40, 40, 40, 40, 40, 40, /* 120 */
4398 40, 40, 40, 40, 40, 40, 40, 46, /* 120 */
4399 46, 46, 40, 40, 40, 40, 40, 40, /* 121 */
4400 46, 46, 40, 40, 40, 40, 40, 40, /* 121 */
4401 46, 46, 40, 40, 40, 40, 40, 40, /* 121 */
4402 46, 46, 40, 40, 40, 46, 46, 46, /* 121 */
4403 4, 4, 7, 11, 15, 4, 4, 46, /* 121 */
4404 7, 7, 7, 7, 7, 15, 15, 46, /* 121 */
4405 46, 46, 46, 46, 46, 46, 46, 46, /* 121 */
4406 46, 46, 46, 46, 46, 15, 46, 46 /* 121 */
4407 };
4409 /* The A table has 124 entries for a total of 496 bytes. */
4411 const uint32 js_A[] = {
4412 0x0001000F, /* 0 Cc, ignorable */
4413 0x0004000F, /* 1 Cc, whitespace */
4414 0x0004000C, /* 2 Zs, whitespace */
4415 0x00000018, /* 3 Po */
4416 0x0006001A, /* 4 Sc, currency */
4417 0x00000015, /* 5 Ps */
4418 0x00000016, /* 6 Pe */
4419 0x00000019, /* 7 Sm */
4420 0x00000014, /* 8 Pd */
4421 0x00036089, /* 9 Nd, identifier part, decimal 16 */
4422 0x0827FF81, /* 10 Lu, hasLower (add 32), identifier start, supradecimal 31 */
4423 0x0000001B, /* 11 Sk */
4424 0x00050017, /* 12 Pc, underscore */
4425 0x0817FF82, /* 13 Ll, hasUpper (subtract 32), identifier start, supradecimal 31 */
4426 0x0000000C, /* 14 Zs */
4427 0x0000001C, /* 15 So */
4428 0x00070182, /* 16 Ll, identifier start */
4429 0x0000600B, /* 17 No, decimal 16 */
4430 0x0000500B, /* 18 No, decimal 8 */
4431 0x0000800B, /* 19 No, strange */
4432 0x08270181, /* 20 Lu, hasLower (add 32), identifier start */
4433 0x08170182, /* 21 Ll, hasUpper (subtract 32), identifier start */
4434 0xE1D70182, /* 22 Ll, hasUpper (subtract -121), identifier start */
4435 0x00670181, /* 23 Lu, hasLower (add 1), identifier start */
4436 0x00570182, /* 24 Ll, hasUpper (subtract 1), identifier start */
4437 0xCE670181, /* 25 Lu, hasLower (add -199), identifier start */
4438 0x3A170182, /* 26 Ll, hasUpper (subtract 232), identifier start */
4439 0xE1E70181, /* 27 Lu, hasLower (add -121), identifier start */
4440 0x4B170182, /* 28 Ll, hasUpper (subtract 300), identifier start */
4441 0x34A70181, /* 29 Lu, hasLower (add 210), identifier start */
4442 0x33A70181, /* 30 Lu, hasLower (add 206), identifier start */
4443 0x33670181, /* 31 Lu, hasLower (add 205), identifier start */
4444 0x32A70181, /* 32 Lu, hasLower (add 202), identifier start */
4445 0x32E70181, /* 33 Lu, hasLower (add 203), identifier start */
4446 0x33E70181, /* 34 Lu, hasLower (add 207), identifier start */
4447 0x34E70181, /* 35 Lu, hasLower (add 211), identifier start */
4448 0x34670181, /* 36 Lu, hasLower (add 209), identifier start */
4449 0x35670181, /* 37 Lu, hasLower (add 213), identifier start */
4450 0x00070181, /* 38 Lu, identifier start */
4451 0x36A70181, /* 39 Lu, hasLower (add 218), identifier start */
4452 0x00070185, /* 40 Lo, identifier start */
4453 0x36670181, /* 41 Lu, hasLower (add 217), identifier start */
4454 0x36E70181, /* 42 Lu, hasLower (add 219), identifier start */
4455 0x00AF0181, /* 43 Lu, hasLower (add 2), hasTitle, identifier start */
4456 0x007F0183, /* 44 Lt, hasUpper (subtract 1), hasLower (add 1), hasTitle, identifier start */
4457 0x009F0182, /* 45 Ll, hasUpper (subtract 2), hasTitle, identifier start */
4458 0x00000000, /* 46 unassigned */
4459 0x34970182, /* 47 Ll, hasUpper (subtract 210), identifier start */
4460 0x33970182, /* 48 Ll, hasUpper (subtract 206), identifier start */
4461 0x33570182, /* 49 Ll, hasUpper (subtract 205), identifier start */
4462 0x32970182, /* 50 Ll, hasUpper (subtract 202), identifier start */
4463 0x32D70182, /* 51 Ll, hasUpper (subtract 203), identifier start */
4464 0x33D70182, /* 52 Ll, hasUpper (subtract 207), identifier start */
4465 0x34570182, /* 53 Ll, hasUpper (subtract 209), identifier start */
4466 0x34D70182, /* 54 Ll, hasUpper (subtract 211), identifier start */
4467 0x35570182, /* 55 Ll, hasUpper (subtract 213), identifier start */
4468 0x36970182, /* 56 Ll, hasUpper (subtract 218), identifier start */
4469 0x36570182, /* 57 Ll, hasUpper (subtract 217), identifier start */
4470 0x36D70182, /* 58 Ll, hasUpper (subtract 219), identifier start */
4471 0x00070084, /* 59 Lm, identifier start */
4472 0x00030086, /* 60 Mn, identifier part */
4473 0x09A70181, /* 61 Lu, hasLower (add 38), identifier start */
4474 0x09670181, /* 62 Lu, hasLower (add 37), identifier start */
4475 0x10270181, /* 63 Lu, hasLower (add 64), identifier start */
4476 0x0FE70181, /* 64 Lu, hasLower (add 63), identifier start */
4477 0x09970182, /* 65 Ll, hasUpper (subtract 38), identifier start */
4478 0x09570182, /* 66 Ll, hasUpper (subtract 37), identifier start */
4479 0x10170182, /* 67 Ll, hasUpper (subtract 64), identifier start */
4480 0x0FD70182, /* 68 Ll, hasUpper (subtract 63), identifier start */
4481 0x0F970182, /* 69 Ll, hasUpper (subtract 62), identifier start */
4482 0x0E570182, /* 70 Ll, hasUpper (subtract 57), identifier start */
4483 0x0BD70182, /* 71 Ll, hasUpper (subtract 47), identifier start */
4484 0x0D970182, /* 72 Ll, hasUpper (subtract 54), identifier start */
4485 0x15970182, /* 73 Ll, hasUpper (subtract 86), identifier start */
4486 0x14170182, /* 74 Ll, hasUpper (subtract 80), identifier start */
4487 0x14270181, /* 75 Lu, hasLower (add 80), identifier start */
4488 0x0C270181, /* 76 Lu, hasLower (add 48), identifier start */
4489 0x0C170182, /* 77 Ll, hasUpper (subtract 48), identifier start */
4490 0x00034089, /* 78 Nd, identifier part, decimal 0 */
4491 0x00000087, /* 79 Me */
4492 0x00030088, /* 80 Mc, identifier part */
4493 0x00037489, /* 81 Nd, identifier part, decimal 26 */
4494 0x00005A0B, /* 82 No, decimal 13 */
4495 0x00006E0B, /* 83 No, decimal 23 */
4496 0x0000740B, /* 84 No, decimal 26 */
4497 0x0000000B, /* 85 No */
4498 0xFE170182, /* 86 Ll, hasUpper (subtract -8), identifier start */
4499 0xFE270181, /* 87 Lu, hasLower (add -8), identifier start */
4500 0xED970182, /* 88 Ll, hasUpper (subtract -74), identifier start */
4501 0xEA970182, /* 89 Ll, hasUpper (subtract -86), identifier start */
4502 0xE7170182, /* 90 Ll, hasUpper (subtract -100), identifier start */
4503 0xE0170182, /* 91 Ll, hasUpper (subtract -128), identifier start */
4504 0xE4170182, /* 92 Ll, hasUpper (subtract -112), identifier start */
4505 0xE0970182, /* 93 Ll, hasUpper (subtract -126), identifier start */
4506 0xFDD70182, /* 94 Ll, hasUpper (subtract -9), identifier start */
4507 0xEDA70181, /* 95 Lu, hasLower (add -74), identifier start */
4508 0xFDE70181, /* 96 Lu, hasLower (add -9), identifier start */
4509 0xEAA70181, /* 97 Lu, hasLower (add -86), identifier start */
4510 0xE7270181, /* 98 Lu, hasLower (add -100), identifier start */
4511 0xFE570182, /* 99 Ll, hasUpper (subtract -7), identifier start */
4512 0xE4270181, /* 100 Lu, hasLower (add -112), identifier start */
4513 0xFE670181, /* 101 Lu, hasLower (add -7), identifier start */
4514 0xE0270181, /* 102 Lu, hasLower (add -128), identifier start */
4515 0xE0A70181, /* 103 Lu, hasLower (add -126), identifier start */
4516 0x00010010, /* 104 Cf, ignorable */
4517 0x0004000D, /* 105 Zl, whitespace */
4518 0x0004000E, /* 106 Zp, whitespace */
4519 0x0000400B, /* 107 No, decimal 0 */
4520 0x0000440B, /* 108 No, decimal 2 */
4521 0x0427438A, /* 109 Nl, hasLower (add 16), identifier start, decimal 1 */
4522 0x0427818A, /* 110 Nl, hasLower (add 16), identifier start, strange */
4523 0x0417638A, /* 111 Nl, hasUpper (subtract 16), identifier start, decimal 17 */
4524 0x0417818A, /* 112 Nl, hasUpper (subtract 16), identifier start, strange */
4525 0x0007818A, /* 113 Nl, identifier start, strange */
4526 0x0000420B, /* 114 No, decimal 1 */
4527 0x0000720B, /* 115 No, decimal 25 */
4528 0x06A0001C, /* 116 So, hasLower (add 26) */
4529 0x0690001C, /* 117 So, hasUpper (subtract 26) */
4530 0x00006C0B, /* 118 No, decimal 22 */
4531 0x0000560B, /* 119 No, decimal 11 */
4532 0x0007738A, /* 120 Nl, identifier start, decimal 25 */
4533 0x0007418A, /* 121 Nl, identifier start, decimal 0 */
4534 0x00000013, /* 122 Cs */
4535 0x00000012 /* 123 Co */
4536 };
4538 const jschar js_uriReservedPlusPound_ucstr[] =
4539 {';', '/', '?', ':', '@', '&', '=', '+', '$', ',', '#', 0};
4540 const jschar js_uriUnescaped_ucstr[] =
4541 {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
4542 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
4543 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
4544 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
4545 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
4546 '-', '_', '.', '!', '~', '*', '\'', '(', ')', 0};
4548 #define URI_CHUNK 64U
4550 /* Concatenate jschars onto an unshared/newborn JSString. */
4551 static JSBool
4552 AddCharsToURI(JSContext *cx, JSString *str, const jschar *chars, size_t length)
4553 {
4554 size_t total;
4556 JS_ASSERT(!JSSTRING_IS_DEPENDENT(str));
4557 total = str->length + length + 1;
4558 if (!str->chars ||
4559 JS_HOWMANY(total, URI_CHUNK) > JS_HOWMANY(str->length + 1, URI_CHUNK)) {
4560 total = JS_ROUNDUP(total, URI_CHUNK);
4561 str->chars = JS_realloc(cx, str->chars, total * sizeof(jschar));
4562 if (!str->chars)
4563 return JS_FALSE;
4564 }
4565 js_strncpy(str->chars + str->length, chars, length);
4566 str->length += length;
4567 str->chars[str->length] = 0;
4568 return JS_TRUE;
4569 }
4571 /*
4572 * ECMA 3, 15.1.3 URI Handling Function Properties
4573 *
4574 * The following are implementations of the algorithms
4575 * given in the ECMA specification for the hidden functions
4576 * 'Encode' and 'Decode'.
4577 */
4578 static JSBool
4579 Encode(JSContext *cx, JSString *str, const jschar *unescapedSet,
4580 const jschar *unescapedSet2, jsval *rval)
4581 {
4582 size_t length, j, k, L;
4583 jschar *chars, c, c2;
4584 uint32 v;
4585 uint8 utf8buf[6];
4586 jschar hexBuf[4];
4587 static const char HexDigits[] = "0123456789ABCDEF"; /* NB: uppercase */
4588 JSString *R;
4590 length = JSSTRING_LENGTH(str);
4591 if (length == 0) {
4592 *rval = STRING_TO_JSVAL(cx->runtime->emptyString);
4593 return JS_TRUE;
4594 }
4596 R = js_NewString(cx, NULL, 0, 0);
4597 if (!R)
4598 return JS_FALSE;
4600 hexBuf[0] = '%';
4601 hexBuf[3] = 0;
4602 chars = JSSTRING_CHARS(str);
4603 for (k = 0; k < length; k++) {
4604 c = chars[k];
4605 if (js_strchr(unescapedSet, c) ||
4606 (unescapedSet2 && js_strchr(unescapedSet2, c))) {
4607 if (!AddCharsToURI(cx, R, &c, 1))
4608 return JS_FALSE;
4609 } else {
4610 if ((c >= 0xDC00) && (c <= 0xDFFF)) {
4611 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
4612 JSMSG_BAD_URI, NULL);
4613 return JS_FALSE;
4614 }
4615 if (c < 0xD800 || c > 0xDBFF) {
4616 v = c;
4617 } else {
4618 k++;
4619 if (k == length) {
4620 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
4621 JSMSG_BAD_URI, NULL);
4622 return JS_FALSE;
4623 }
4624 c2 = chars[k];
4625 if ((c2 < 0xDC00) || (c2 > 0xDFFF)) {
4626 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
4627 JSMSG_BAD_URI, NULL);
4628 return JS_FALSE;
4629 }
4630 v = ((c - 0xD800) << 10) + (c2 - 0xDC00) + 0x10000;
4631 }
4632 L = js_OneUcs4ToUtf8Char(utf8buf, v);
4633 for (j = 0; j < L; j++) {
4634 hexBuf[1] = HexDigits[utf8buf[j] >> 4];
4635 hexBuf[2] = HexDigits[utf8buf[j] & 0xf];
4636 if (!AddCharsToURI(cx, R, hexBuf, 3))
4637 return JS_FALSE;
4638 }
4639 }
4640 }
4642 /*
4643 * Shrinking realloc can fail (e.g., with a BSD-style allocator), but we
4644 * don't worry about that case here. Worst case, R hangs onto URI_CHUNK-1
4645 * more jschars than it needs.
4646 */
4647 chars = (jschar *) JS_realloc(cx, R->chars, (R->length+1) * sizeof(jschar));
4648 if (chars)
4649 R->chars = chars;
4650 *rval = STRING_TO_JSVAL(R);
4651 return JS_TRUE;
4652 }
4654 static JSBool
4655 Decode(JSContext *cx, JSString *str, const jschar *reservedSet, jsval *rval)
4656 {
4657 size_t length, start, k;
4658 jschar *chars, c, H;
4659 uint32 v;
4660 jsuint B;
4661 uint8 octets[6];
4662 JSString *R;
4663 intN j, n;
4665 length = JSSTRING_LENGTH(str);
4666 if (length == 0) {
4667 *rval = STRING_TO_JSVAL(cx->runtime->emptyString);
4668 return JS_TRUE;
4669 }
4671 R = js_NewString(cx, NULL, 0, 0);
4672 if (!R)
4673 return JS_FALSE;
4675 chars = JSSTRING_CHARS(str);
4676 for (k = 0; k < length; k++) {
4677 c = chars[k];
4678 if (c == '%') {
4679 start = k;
4680 if ((k + 2) >= length)
4681 goto bad;
4682 if (!JS7_ISHEX(chars[k+1]) || !JS7_ISHEX(chars[k+2]))
4683 goto bad;
4684 B = JS7_UNHEX(chars[k+1]) * 16 + JS7_UNHEX(chars[k+2]);
4685 k += 2;
4686 if (!(B & 0x80)) {
4687 c = (jschar)B;
4688 } else {
4689 n = 1;
4690 while (B & (0x80 >> n))
4691 n++;
4692 if (n == 1 || n > 6)
4693 goto bad;
4694 octets[0] = (uint8)B;
4695 if (k + 3 * (n - 1) >= length)
4696 goto bad;
4697 for (j = 1; j < n; j++) {
4698 k++;
4699 if (chars[k] != '%')
4700 goto bad;
4701 if (!JS7_ISHEX(chars[k+1]) || !JS7_ISHEX(chars[k+2]))
4702 goto bad;
4703 B = JS7_UNHEX(chars[k+1]) * 16 + JS7_UNHEX(chars[k+2]);
4704 if ((B & 0xC0) != 0x80)
4705 goto bad;
4706 k += 2;
4707 octets[j] = (char)B;
4708 }
4709 v = Utf8ToOneUcs4Char(octets, n);
4710 if (v >= 0x10000) {
4711 v -= 0x10000;
4712 if (v > 0xFFFFF)
4713 goto bad;
4714 c = (jschar)((v & 0x3FF) + 0xDC00);
4715 H = (jschar)((v >> 10) + 0xD800);
4716 if (!AddCharsToURI(cx, R, &H, 1))
4717 return JS_FALSE;
4718 } else {
4719 c = (jschar)v;
4720 }
4721 }
4722 if (js_strchr(reservedSet, c)) {
4723 if (!AddCharsToURI(cx, R, &chars[start], (k - start + 1)))
4724 return JS_FALSE;
4725 } else {
4726 if (!AddCharsToURI(cx, R, &c, 1))
4727 return JS_FALSE;
4728 }
4729 } else {
4730 if (!AddCharsToURI(cx, R, &c, 1))
4731 return JS_FALSE;
4732 }
4733 }
4735 /*
4736 * Shrinking realloc can fail (e.g., with a BSD-style allocator), but we
4737 * don't worry about that case here. Worst case, R hangs onto URI_CHUNK-1
4738 * more jschars than it needs.
4739 */
4740 chars = (jschar *) JS_realloc(cx, R->chars, (R->length+1) * sizeof(jschar));
4741 if (chars)
4742 R->chars = chars;
4743 *rval = STRING_TO_JSVAL(R);
4744 return JS_TRUE;
4746 bad:
4747 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_BAD_URI);
4748 return JS_FALSE;
4749 }
4751 static JSBool
4752 str_decodeURI(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
4753 jsval *rval)
4754 {
4755 JSString *str;
4757 str = js_ValueToString(cx, argv[0]);
4758 if (!str)
4759 return JS_FALSE;
4760 argv[0] = STRING_TO_JSVAL(str);
4761 return Decode(cx, str, js_uriReservedPlusPound_ucstr, rval);
4762 }
4764 static JSBool
4765 str_decodeURI_Component(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
4766 jsval *rval)
4767 {
4768 JSString *str;
4770 str = js_ValueToString(cx, argv[0]);
4771 if (!str)
4772 return JS_FALSE;
4773 argv[0] = STRING_TO_JSVAL(str);
4774 return Decode(cx, str, js_empty_ucstr, rval);
4775 }
4777 static JSBool
4778 str_encodeURI(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
4779 jsval *rval)
4780 {
4781 JSString *str;
4783 str = js_ValueToString(cx, argv[0]);
4784 if (!str)
4785 return JS_FALSE;
4786 argv[0] = STRING_TO_JSVAL(str);
4787 return Encode(cx, str, js_uriReservedPlusPound_ucstr, js_uriUnescaped_ucstr,
4788 rval);
4789 }
4791 static JSBool
4792 str_encodeURI_Component(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
4793 jsval *rval)
4794 {
4795 JSString *str;
4797 str = js_ValueToString(cx, argv[0]);
4798 if (!str)
4799 return JS_FALSE;
4800 argv[0] = STRING_TO_JSVAL(str);
4801 return Encode(cx, str, js_uriUnescaped_ucstr, NULL, rval);
4802 }
4804 /*
4805 * Convert one UCS-4 char and write it into a UTF-8 buffer, which must be at
4806 * least 6 bytes long. Return the number of UTF-8 bytes of data written.
4807 */
4808 int
4809 js_OneUcs4ToUtf8Char(uint8 *utf8Buffer, uint32 ucs4Char)
4810 {
4811 int utf8Length = 1;
4813 JS_ASSERT(ucs4Char <= 0x7FFFFFFF);
4814 if (ucs4Char < 0x80) {
4815 *utf8Buffer = (uint8)ucs4Char;
4816 } else {
4817 int i;
4818 uint32 a = ucs4Char >> 11;
4819 utf8Length = 2;
4820 while (a) {
4821 a >>= 5;
4822 utf8Length++;
4823 }
4824 i = utf8Length;
4825 while (--i) {
4826 utf8Buffer[i] = (uint8)((ucs4Char & 0x3F) | 0x80);
4827 ucs4Char >>= 6;
4828 }
4829 *utf8Buffer = (uint8)(0x100 - (1 << (8-utf8Length)) + ucs4Char);
4830 }
4831 return utf8Length;
4832 }
4834 /*
4835 * Convert a utf8 character sequence into a UCS-4 character and return that
4836 * character. It is assumed that the caller already checked that the sequence
4837 * is valid.
4838 */
4839 static uint32
4840 Utf8ToOneUcs4Char(const uint8 *utf8Buffer, int utf8Length)
4841 {
4842 uint32 ucs4Char;
4843 uint32 minucs4Char;
4844 /* from Unicode 3.1, non-shortest form is illegal */
4845 static const uint32 minucs4Table[] = {
4846 0x00000080, 0x00000800, 0x0001000, 0x0020000, 0x0400000
4847 };
4849 JS_ASSERT(utf8Length >= 1 && utf8Length <= 6);
4850 if (utf8Length == 1) {
4851 ucs4Char = *utf8Buffer;
4852 JS_ASSERT(!(ucs4Char & 0x80));
4853 } else {
4854 JS_ASSERT((*utf8Buffer & (0x100 - (1 << (7-utf8Length)))) ==
4855 (0x100 - (1 << (8-utf8Length))));
4856 ucs4Char = *utf8Buffer++ & ((1<<(7-utf8Length))-1);
4857 minucs4Char = minucs4Table[utf8Length-2];
4858 while (--utf8Length) {
4859 JS_ASSERT((*utf8Buffer & 0xC0) == 0x80);
4860 ucs4Char = ucs4Char<<6 | (*utf8Buffer++ & 0x3F);
4861 }
4862 if (ucs4Char < minucs4Char ||
4863 ucs4Char == 0xFFFE || ucs4Char == 0xFFFF) {
4864 ucs4Char = 0xFFFD;
4865 }
4866 }
4867 return ucs4Char;
4868 }