3 ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
5 ** Portions taken verbatim or adapted from the Lua interpreter.
6 ** Copyright (C) 1994-2008 Lua.org, PUC-Rio. See Copyright Notice in lua.h
21 /* -- String interning ---------------------------------------------------- */
23 /* Ordered compare of strings. Assumes string data is 4-byte aligned. */
24 int32_t LJ_FASTCALL
lj_str_cmp(GCstr
*a
, GCstr
*b
)
26 MSize i
, n
= a
->len
> b
->len
? b
->len
: a
->len
;
27 for (i
= 0; i
< n
; i
+= 4) {
28 /* Note: innocuous access up to end of string + 3. */
29 uint32_t va
= *(const uint32_t *)(strdata(a
)+i
);
30 uint32_t vb
= *(const uint32_t *)(strdata(b
)+i
);
33 va
= lj_bswap(va
); vb
= lj_bswap(vb
);
36 if ((int32_t)i
>= -3) {
37 va
>>= 32+(i
<<3); vb
>>= 32+(i
<<3);
40 return va
< vb
? -1 : 1;
43 return (int32_t)(a
->len
- b
->len
);
46 /* Fast string data comparison. Caveat: unaligned access to 1st string! */
47 static LJ_AINLINE
int str_fastcmp(const char *a
, const char *b
, MSize len
)
51 lua_assert((((uintptr_t)a
+len
-1) & (LJ_PAGESIZE
-1)) <= LJ_PAGESIZE
-4);
52 do { /* Note: innocuous access up to end of string + 3. */
53 uint32_t v
= lj_getu32(a
+i
) ^ *(const uint32_t *)(b
+i
);
57 return (int32_t)i
>= -3 ? (v
<< (32+(i
<<3))) : 1;
59 return (int32_t)i
>= -3 ? (v
>> (32+(i
<<3))) : 1;
67 /* Resize the string hash table (grow and shrink). */
68 void lj_str_resize(lua_State
*L
, MSize newmask
)
70 global_State
*g
= G(L
);
73 if (g
->gc
.state
== GCSsweepstring
|| newmask
>= LJ_MAX_STRTAB
-1)
74 return; /* No resizing during GC traversal or if already too big. */
75 newhash
= lj_mem_newvec(L
, newmask
+1, GCRef
);
76 memset(newhash
, 0, (newmask
+1)*sizeof(GCRef
));
77 for (i
= g
->strmask
; i
!= ~(MSize
)0; i
--) { /* Rehash old table. */
78 GCobj
*p
= gcref(g
->strhash
[i
]);
79 while (p
) { /* Follow each hash chain and reinsert all strings. */
80 MSize h
= gco2str(p
)->hash
& newmask
;
81 GCobj
*next
= gcnext(p
);
82 /* NOBARRIER: The string table is a GC root. */
83 setgcrefr(p
->gch
.nextgc
, newhash
[h
]);
84 setgcref(newhash
[h
], p
);
88 lj_mem_freevec(g
, g
->strhash
, g
->strmask
+1, GCRef
);
94 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
97 #if !defined(LUAI_HASHLIMIT)
98 #define LUAI_HASHLIMIT 5
101 #define cast(t, exp) ((t)(exp))
102 int luajittex_choose_hash_function
= 0 ;
103 /* Intern a string and return string object. */
104 GCstr
*lj_str_new(lua_State
*L
, const char *str
, size_t lenx
)
109 MSize len
= (MSize
)lenx
;
113 if (lenx
>= LJ_MAX_STR
)
114 lj_err_msg(L
, LJ_ERR_STROV
);
119 if (luajittex_choose_hash_function
==0) {
120 /* Lua 5.1.5 hash function */
121 /* for 5.2 max methods we also need to patch the vm eq */
122 step
= (len
>>LUAI_HASHLIMIT
)+1; /* if string is too long, don't hash all its chars */
123 for (l1
=len
; l1
>=step
; l1
-=step
) /* compute hash */
124 h
= h
^ ((h
<<5)+(h
>>2)+cast(unsigned char, str
[l1
-1]));
126 /* LuaJIT 2.0.2 hash function */
127 /* Compute string hash. Constants taken from lookup3 hash by Bob Jenkins. */
128 if (len
>= 4) { /* Caveat: unaligned access! */
130 h
^= lj_getu32(str
+len
-4);
131 b
= lj_getu32(str
+(len
>>1)-2);
132 h
^= b
; h
-= lj_rol(b
, 14);
133 b
+= lj_getu32(str
+(len
>>2)-1);
134 } else if (len
> 0) {
135 a
= *(const uint8_t *)str
;
136 h
^= *(const uint8_t *)(str
+len
-1);
137 b
= *(const uint8_t *)(str
+(len
>>1));
138 h
^= b
; h
-= lj_rol(b
, 14);
140 /* Already done, kept for reference */
143 a
^= h
; a
-= lj_rol(h
, 11);
144 b
^= a
; b
-= lj_rol(a
, 25);
145 h
^= b
; h
-= lj_rol(b
, 16);
149 /* Check if the string has already been interned. */
150 o
= gcref(g
->strhash
[h
& g
->strmask
]);
151 if (LJ_LIKELY((((uintptr_t)str
+len
-1) & (LJ_PAGESIZE
-1)) <= LJ_PAGESIZE
-4)) {
153 GCstr
*sx
= gco2str(o
);
154 if (sx
->len
== len
&& str_fastcmp(str
, strdata(sx
), len
) == 0) {
155 /* Resurrect if dead. Can only happen with fixstring() (keywords). */
156 if (isdead(g
, o
)) flipwhite(o
);
157 return sx
; /* Return existing string. */
161 } else { /* Slow path: end of string is too close to a page boundary. */
163 GCstr
*sx
= gco2str(o
);
164 if (sx
->len
== len
&& memcmp(str
, strdata(sx
), len
) == 0) {
165 /* Resurrect if dead. Can only happen with fixstring() (keywords). */
166 if (isdead(g
, o
)) flipwhite(o
);
167 return sx
; /* Return existing string. */
172 /* Nope, create a new string. */
173 s
= lj_mem_newt(L
, sizeof(GCstr
)+len
+1, GCstr
);
179 memcpy(strdatawr(s
), str
, len
);
180 strdatawr(s
)[len
] = '\0'; /* Zero-terminate string. */
181 /* Add it to string hash table. */
183 s
->nextgc
= g
->strhash
[h
];
184 /* NOBARRIER: The string table is a GC root. */
185 setgcref(g
->strhash
[h
], obj2gco(s
));
186 if (g
->strnum
++ > g
->strmask
) /* Allow a 100% load factor. */
187 lj_str_resize(L
, (g
->strmask
<<1)+1); /* Grow string table. */
188 return s
; /* Return newly interned string. */
191 void LJ_FASTCALL
lj_str_free(global_State
*g
, GCstr
*s
)
194 lj_mem_free(g
, s
, sizestring(s
));
197 /* -- Type conversions ---------------------------------------------------- */
199 /* Print number to buffer. Canonicalizes non-finite values. */
200 size_t LJ_FASTCALL
lj_str_bufnum(char *s
, cTValue
*o
)
202 if (LJ_LIKELY((o
->u32
.hi
<< 1) < 0xffe00000)) { /* Finite? */
205 if (tvismzero(o
)) { s
[0] = '-'; s
[1] = '0'; return 2; }
207 return (size_t)lua_number2str(s
, n
);
208 } else if (((o
->u32
.hi
& 0x000fffff) | o
->u32
.lo
) != 0) {
209 s
[0] = 'n'; s
[1] = 'a'; s
[2] = 'n'; return 3;
210 } else if ((o
->u32
.hi
& 0x80000000) == 0) {
211 s
[0] = 'i'; s
[1] = 'n'; s
[2] = 'f'; return 3;
213 s
[0] = '-'; s
[1] = 'i'; s
[2] = 'n'; s
[3] = 'f'; return 4;
217 /* Print integer to buffer. Returns pointer to start. */
218 char * LJ_FASTCALL
lj_str_bufint(char *p
, int32_t k
)
220 uint32_t u
= (uint32_t)(k
< 0 ? -k
: k
);
222 do { *--p
= (char)('0' + u
% 10); } while (u
/= 10);
223 if (k
< 0) *--p
= '-';
227 /* Convert number to string. */
228 GCstr
* LJ_FASTCALL
lj_str_fromnum(lua_State
*L
, const lua_Number
*np
)
230 char buf
[LJ_STR_NUMBUF
];
231 size_t len
= lj_str_bufnum(buf
, (TValue
*)np
);
232 return lj_str_new(L
, buf
, len
);
235 /* Convert integer to string. */
236 GCstr
* LJ_FASTCALL
lj_str_fromint(lua_State
*L
, int32_t k
)
239 char *p
= lj_str_bufint(s
, k
);
240 return lj_str_new(L
, p
, (size_t)(s
+sizeof(s
)-p
));
243 GCstr
* LJ_FASTCALL
lj_str_fromnumber(lua_State
*L
, cTValue
*o
)
245 return tvisint(o
) ? lj_str_fromint(L
, intV(o
)) : lj_str_fromnum(L
, &o
->n
);
248 /* -- String formatting --------------------------------------------------- */
250 static void addstr(lua_State
*L
, SBuf
*sb
, const char *str
, MSize len
)
254 if (sb
->n
+ len
> sb
->sz
) {
255 MSize sz
= sb
->sz
* 2;
256 while (sb
->n
+ len
> sz
) sz
= sz
* 2;
257 lj_str_resizebuf(L
, sb
, sz
);
261 for (i
= 0; i
< len
; i
++) p
[i
] = str
[i
];
264 static void addchar(lua_State
*L
, SBuf
*sb
, int c
)
266 if (sb
->n
+ 1 > sb
->sz
) {
267 MSize sz
= sb
->sz
* 2;
268 lj_str_resizebuf(L
, sb
, sz
);
270 sb
->buf
[sb
->n
++] = (char)c
;
273 /* Push formatted message as a string object to Lua stack. va_list variant. */
274 const char *lj_str_pushvf(lua_State
*L
, const char *fmt
, va_list argp
)
276 SBuf
*sb
= &G(L
)->tmpbuf
;
277 lj_str_needbuf(L
, sb
, (MSize
)strlen(fmt
));
280 const char *e
= strchr(fmt
, '%');
281 if (e
== NULL
) break;
282 addstr(L
, sb
, fmt
, (MSize
)(e
-fmt
));
283 /* This function only handles %s, %c, %d, %f and %p formats. */
286 const char *s
= va_arg(argp
, char *);
287 if (s
== NULL
) s
= "(null)";
288 addstr(L
, sb
, s
, (MSize
)strlen(s
));
292 addchar(L
, sb
, va_arg(argp
, int));
295 char buf
[LJ_STR_INTBUF
];
296 char *p
= lj_str_bufint(buf
, va_arg(argp
, int32_t));
297 addstr(L
, sb
, p
, (MSize
)(buf
+LJ_STR_INTBUF
-p
));
301 char buf
[LJ_STR_NUMBUF
];
304 tv
.n
= (lua_Number
)(va_arg(argp
, LUAI_UACNUMBER
));
305 len
= (MSize
)lj_str_bufnum(buf
, &tv
);
306 addstr(L
, sb
, buf
, len
);
310 #define FMTP_CHARS (2*sizeof(ptrdiff_t))
311 char buf
[2+FMTP_CHARS
];
312 ptrdiff_t p
= (ptrdiff_t)(va_arg(argp
, void *));
313 ptrdiff_t i
, lasti
= 2+FMTP_CHARS
;
315 addstr(L
, sb
, "NULL", 4);
319 /* Shorten output for 64 bit pointers. */
320 lasti
= 2+2*4+((p
>> 32) ? 2+2*(lj_fls((uint32_t)(p
>> 32))>>3) : 0);
324 for (i
= lasti
-1; i
>= 2; i
--, p
>>= 4)
325 buf
[i
] = "0123456789abcdef"[(p
& 15)];
326 addstr(L
, sb
, buf
, (MSize
)lasti
);
334 addchar(L
, sb
, e
[1]);
339 addstr(L
, sb
, fmt
, (MSize
)strlen(fmt
));
340 setstrV(L
, L
->top
, lj_str_new(L
, sb
->buf
, sb
->n
));
342 return strVdata(L
->top
- 1);
345 /* Push formatted message as a string object to Lua stack. Vararg variant. */
346 const char *lj_str_pushf(lua_State
*L
, const char *fmt
, ...)
351 msg
= lj_str_pushvf(L
, fmt
, argp
);
356 /* -- Buffer handling ----------------------------------------------------- */
358 char *lj_str_needbuf(lua_State
*L
, SBuf
*sb
, MSize sz
)
361 if (sz
< LJ_MIN_SBUF
) sz
= LJ_MIN_SBUF
;
362 lj_str_resizebuf(L
, sb
, sz
);