1/*
2** $Id: lstrlib.c,v 1.254 2016/12/22 13:08:50 roberto Exp $
3** Standard library for string operations and pattern-matching
4** Modified by the Kepler Project and the LOVE Development Team to work with
5** Lua 5.1's API
6*/
7
8/*********************************************************************
9 * The MIT License (MIT)
10 *
11 * Copyright (c) 2015 Kepler Project.
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining a copy of
14 * this software and associated documentation files (the "Software"), to deal in
15 * the Software without restriction, including without limitation the rights to
16 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
17 * the Software, and to permit persons to whom the Software is furnished to do so,
18 * subject to the following conditions:
19
20 * The above copyright notice and this permission notice shall be included in all
21 * copies or substantial portions of the Software.
22
23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
25 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
26 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
27 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
28 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 *********************************************************************/
30
31/*********************************************************************
32 * This file contains parts of Lua 5.2's and Lua 5.3's source code:
33 *
34 * Copyright (C) 1994-2014 Lua.org, PUC-Rio.
35 *
36 * Permission is hereby granted, free of charge, to any person obtaining
37 * a copy of this software and associated documentation files (the
38 * "Software"), to deal in the Software without restriction, including
39 * without limitation the rights to use, copy, modify, merge, publish,
40 * distribute, sublicense, and/or sell copies of the Software, and to
41 * permit persons to whom the Software is furnished to do so, subject to
42 * the following conditions:
43 *
44 * The above copyright notice and this permission notice shall be
45 * included in all copies or substantial portions of the Software.
46 *
47 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
48 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
49 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
50 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
51 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
52 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
53 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
54 *********************************************************************/
55
56#include "lprefix.h"
57
58
59#include <ctype.h>
60#include <float.h>
61#include <limits.h>
62#include <stddef.h>
63#include <stdlib.h>
64#include <string.h>
65
66#include "lua.h"
67
68#include "lauxlib.h"
69#include "lualib.h"
70#include "lstrlib.h"
71
72#if LUA_VERSION_NUM == 501
73typedef size_t lua_Unsigned;
74#endif
75
76#if LUA_VERSION_NUM >= 504
77# define LUAL_BUFFER53_BUFFER(B) (B)->b.b
78#elif LUA_VERSION_NUM == 501
79# define LUAL_BUFFER53_BUFFER(B) (B)->b.buffer
80#else
81# define LUAL_BUFFER53_BUFFER(B) (B)->b.initb
82#endif
83
84static void luaL_buffinit_53 (lua_State *L, luaL_Buffer_53 *B) {
85#if LUA_VERSION_NUM == 501
86 /* make it crash if used via pointer to a 5.1-style luaL_Buffer */
87 B->b.p = NULL;
88 B->b.L = NULL;
89 B->b.lvl = 0;
90 /* reuse the buffer from the 5.1-style luaL_Buffer though! */
91 B->ptr = B->b.buffer;
92 B->capacity = LUAL_BUFFERSIZE;
93 B->nelems = 0;
94 B->L2 = L;
95#else
96 return luaL_buffinit(L, (luaL_Buffer*) B);
97#endif
98}
99
100
101static char *luaL_prepbuffsize_53 (luaL_Buffer_53 *B, size_t s) {
102#if LUA_VERSION_NUM == 501
103 if (B->capacity - B->nelems < s) { /* needs to grow */
104 char* newptr = NULL;
105 size_t newcap = B->capacity * 2;
106 if (newcap - B->nelems < s)
107 newcap = B->nelems + s;
108 if (newcap < B->capacity) /* overflow */
109 luaL_error(B->L2, "buffer too large");
110 newptr = (char*)lua_newuserdata(B->L2, newcap);
111 memcpy(newptr, B->ptr, B->nelems);
112 if (B->ptr != B->b.buffer)
113 lua_replace(B->L2, -2); /* remove old buffer */
114 B->ptr = newptr;
115 B->capacity = newcap;
116 }
117 return B->ptr+B->nelems;
118#else
119 return luaL_prepbuffsize((luaL_Buffer*) B, s);
120#endif
121}
122
123
124#define luaL_addsize_53(B, s) \
125 ((B)->nelems += (s))
126
127#define luaL_addchar_53(B, c) \
128 ((void)((B)->nelems < (B)->capacity || luaL_prepbuffsize_53((B), 1)), \
129 ((B)->ptr[(B)->nelems++] = (c)))
130
131
132static void luaL_addlstring_53 (luaL_Buffer_53 *B, const char *s, size_t l) {
133 memcpy(luaL_prepbuffsize_53(B, l), s, l);
134 luaL_addsize_53(B, l);
135}
136
137
138void lua53_pushresult (luaL_Buffer_53 *B) {
139 lua_pushlstring(B->L2, B->ptr, B->nelems);
140 if (B->ptr != LUAL_BUFFER53_BUFFER(B))
141 lua_replace(B->L2, -2); /* remove userdata buffer */
142}
143
144void lua53_cleanupbuffer (luaL_Buffer_53 *B) {
145 if (B->ptr != LUAL_BUFFER53_BUFFER(B))
146 lua_replace(B->L2, -1); /* remove userdata buffer */
147}
148
149/*
150** Some sizes are better limited to fit in 'int', but must also fit in
151** 'size_t'. (We assume that 'lua_Integer' cannot be smaller than 'int'.)
152*/
153#define MAX_SIZET ((size_t)(~(size_t)0))
154
155#define MAXSIZE \
156 (sizeof(size_t) < sizeof(int) ? MAX_SIZET : (size_t)(INT_MAX))
157
158
159/* translate a relative string position: negative means back from end */
160static lua_Integer posrelat (lua_Integer pos, size_t len) {
161 if (pos >= 0) return pos;
162 else if (0u - (size_t)pos > len) return 0;
163 else return (lua_Integer)len + pos + 1;
164}
165
166
167/*
168** {======================================================
169** PACK/UNPACK
170** =======================================================
171*/
172
173
174/* value used for padding */
175#if !defined(LUAL_PACKPADBYTE)
176#define LUAL_PACKPADBYTE 0x00
177#endif
178
179/* maximum size for the binary representation of an integer */
180#define MAXINTSIZE 16
181
182/* number of bits in a character */
183#define NB CHAR_BIT
184
185/* mask for one character (NB 1's) */
186#define MC ((1 << NB) - 1)
187
188/* size of a lua_Integer */
189#define SZINT ((int)sizeof(lua_Integer))
190
191
192/* dummy union to get native endianness */
193static const union {
194 int dummy;
195 char little; /* true iff machine is little endian */
196} nativeendian = {1};
197
198
199/* dummy structure to get native alignment requirements */
200struct cD {
201 char c;
202 union { double d; void *p; lua_Integer i; lua_Number n; } u;
203};
204
205#define MAXALIGN (offsetof(struct cD, u))
206
207
208/*
209** Union for serializing floats
210*/
211typedef union Ftypes {
212 float f;
213 double d;
214 lua_Number n;
215 char buff[5 * sizeof(lua_Number)]; /* enough for any float type */
216} Ftypes;
217
218
219/*
220** information to pack/unpack stuff
221*/
222typedef struct Header {
223 lua_State *L;
224 int islittle;
225 int maxalign;
226} Header;
227
228
229/*
230** options for pack/unpack
231*/
232typedef enum KOption {
233 Kint, /* signed integers */
234 Kuint, /* unsigned integers */
235 Kfloat, /* floating-point numbers */
236 Kchar, /* fixed-length strings */
237 Kstring, /* strings with prefixed length */
238 Kzstr, /* zero-terminated strings */
239 Kpadding, /* padding */
240 Kpaddalign, /* padding for alignment */
241 Knop /* no-op (configuration or spaces) */
242} KOption;
243
244
245/*
246** Read an integer numeral from string 'fmt' or return 'df' if
247** there is no numeral
248*/
249static int digit (int c) { return '0' <= c && c <= '9'; }
250
251static int getnum (const char **fmt, int df) {
252 if (!digit(**fmt)) /* no number? */
253 return df; /* return default value */
254 else {
255 int a = 0;
256 do {
257 a = a*10 + (*((*fmt)++) - '0');
258 } while (digit(**fmt) && a <= ((int)MAXSIZE - 9)/10);
259 return a;
260 }
261}
262
263
264/*
265** Read an integer numeral and raises an error if it is larger
266** than the maximum size for integers.
267*/
268static int getnumlimit (Header *h, const char **fmt, int df) {
269 int sz = getnum(fmt, df);
270 if (sz > MAXINTSIZE || sz <= 0)
271 luaL_error(h->L, "integral size (%d) out of limits [1,%d]",
272 sz, MAXINTSIZE);
273 return sz;
274}
275
276
277/*
278** Initialize Header
279*/
280static void initheader (lua_State *L, Header *h) {
281 h->L = L;
282 h->islittle = nativeendian.little;
283 h->maxalign = 1;
284}
285
286
287/*
288** Read and classify next option. 'size' is filled with option's size.
289*/
290static KOption getoption (Header *h, const char **fmt, int *size) {
291 int opt = *((*fmt)++);
292 *size = 0; /* default */
293 switch (opt) {
294 case 'b': *size = sizeof(char); return Kint;
295 case 'B': *size = sizeof(char); return Kuint;
296 case 'h': *size = sizeof(short); return Kint;
297 case 'H': *size = sizeof(short); return Kuint;
298 case 'l': *size = sizeof(long); return Kint;
299 case 'L': *size = sizeof(long); return Kuint;
300 case 'j': *size = sizeof(lua_Integer); return Kint;
301 case 'J': *size = sizeof(lua_Integer); return Kuint;
302 case 'T': *size = sizeof(size_t); return Kuint;
303 case 'f': *size = sizeof(float); return Kfloat;
304 case 'd': *size = sizeof(double); return Kfloat;
305 case 'n': *size = sizeof(lua_Number); return Kfloat;
306 case 'i': *size = getnumlimit(h, fmt, sizeof(int)); return Kint;
307 case 'I': *size = getnumlimit(h, fmt, sizeof(int)); return Kuint;
308 case 's': *size = getnumlimit(h, fmt, sizeof(size_t)); return Kstring;
309 case 'c':
310 *size = getnum(fmt, -1);
311 if (*size == -1)
312 luaL_error(h->L, "missing size for format option 'c'");
313 return Kchar;
314 case 'z': return Kzstr;
315 case 'x': *size = 1; return Kpadding;
316 case 'X': return Kpaddalign;
317 case ' ': break;
318 case '<': h->islittle = 1; break;
319 case '>': h->islittle = 0; break;
320 case '=': h->islittle = nativeendian.little; break;
321 case '!': h->maxalign = getnumlimit(h, fmt, MAXALIGN); break;
322 default: luaL_error(h->L, "invalid format option '%c'", opt);
323 }
324 return Knop;
325}
326
327
328/*
329** Read, classify, and fill other details about the next option.
330** 'psize' is filled with option's size, 'notoalign' with its
331** alignment requirements.
332** Local variable 'size' gets the size to be aligned. (Kpadal option
333** always gets its full alignment, other options are limited by
334** the maximum alignment ('maxalign'). Kchar option needs no alignment
335** despite its size.
336*/
337static KOption getdetails (Header *h, size_t totalsize,
338 const char **fmt, int *psize, int *ntoalign) {
339 KOption opt = getoption(h, fmt, psize);
340 int align = *psize; /* usually, alignment follows size */
341 if (opt == Kpaddalign) { /* 'X' gets alignment from following option */
342 if (**fmt == '\0' || getoption(h, fmt, &align) == Kchar || align == 0)
343 luaL_argerror(h->L, 1, "invalid next option for option 'X'");
344 }
345 if (align <= 1 || opt == Kchar) /* need no alignment? */
346 *ntoalign = 0;
347 else {
348 if (align > h->maxalign) /* enforce maximum alignment */
349 align = h->maxalign;
350 if ((align & (align - 1)) != 0) /* is 'align' not a power of 2? */
351 luaL_argerror(h->L, 1, "format asks for alignment not power of 2");
352 *ntoalign = (align - (int)(totalsize & (align - 1))) & (align - 1);
353 }
354 return opt;
355}
356
357
358/*
359** Pack integer 'n' with 'size' bytes and 'islittle' endianness.
360** The final 'if' handles the case when 'size' is larger than
361** the size of a Lua integer, correcting the extra sign-extension
362** bytes if necessary (by default they would be zeros).
363*/
364static void packint (luaL_Buffer_53 *b, lua_Unsigned n,
365 int islittle, int size, int neg) {
366 char *buff = luaL_prepbuffsize_53(b, size);
367 int i;
368 buff[islittle ? 0 : size - 1] = (char)(n & MC); /* first byte */
369 for (i = 1; i < size; i++) {
370 n >>= NB;
371 buff[islittle ? i : size - 1 - i] = (char)(n & MC);
372 }
373 if (neg && size > SZINT) { /* negative number need sign extension? */
374 for (i = SZINT; i < size; i++) /* correct extra bytes */
375 buff[islittle ? i : size - 1 - i] = (char)MC;
376 }
377 luaL_addsize_53(b, size); /* add result to buffer */
378}
379
380
381/*
382** Copy 'size' bytes from 'src' to 'dest', correcting endianness if
383** given 'islittle' is different from native endianness.
384*/
385static void copywithendian (volatile char *dest, volatile const char *src,
386 int size, int islittle) {
387 if (islittle == nativeendian.little) {
388 while (size-- != 0)
389 *(dest++) = *(src++);
390 }
391 else {
392 dest += size - 1;
393 while (size-- != 0)
394 *(dest--) = *(src++);
395 }
396}
397
398
399void lua53_str_pack (lua_State *L, const char *fmt, int startidx, luaL_Buffer_53 *b) {
400 Header h;
401 int arg = startidx - 1; /* current argument to pack */
402 size_t totalsize = 0; /* accumulate total size of result */
403 initheader(L, &h);
404 lua_pushnil(L); /* mark to separate arguments from string buffer */
405 luaL_buffinit_53(L, b);
406 while (*fmt != '\0') {
407 int size, ntoalign;
408 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign);
409 totalsize += ntoalign + size;
410 while (ntoalign-- > 0)
411 luaL_addchar_53(b, LUAL_PACKPADBYTE); /* fill alignment */
412 arg++;
413 switch (opt) {
414 case Kint: { /* signed integers */
415 lua_Integer n = luaL_checkinteger(L, arg);
416 if (size < SZINT) { /* need overflow check? */
417 lua_Integer lim = (lua_Integer)1 << ((size * NB) - 1);
418 luaL_argcheck(L, -lim <= n && n < lim, arg, "integer overflow");
419 }
420 packint(b, (lua_Unsigned)n, h.islittle, size, (n < 0));
421 break;
422 }
423 case Kuint: { /* unsigned integers */
424 lua_Integer n = luaL_checkinteger(L, arg);
425 if (size < SZINT) /* need overflow check? */
426 luaL_argcheck(L, (lua_Unsigned)n < ((lua_Unsigned)1 << (size * NB)),
427 arg, "unsigned overflow");
428 packint(b, (lua_Unsigned)n, h.islittle, size, 0);
429 break;
430 }
431 case Kfloat: { /* floating-point options */
432 volatile Ftypes u;
433 char *buff = luaL_prepbuffsize_53(b, size);
434 lua_Number n = luaL_checknumber(L, arg); /* get argument */
435 if (size == sizeof(u.f)) u.f = (float)n; /* copy it into 'u' */
436 else if (size == sizeof(u.d)) u.d = (double)n;
437 else u.n = n;
438 /* move 'u' to final result, correcting endianness if needed */
439 copywithendian(buff, u.buff, size, h.islittle);
440 luaL_addsize_53(b, size);
441 break;
442 }
443 case Kchar: { /* fixed-size string */
444 size_t len;
445 const char *s = luaL_checklstring(L, arg, &len);
446 luaL_argcheck(L, len <= (size_t)size, arg,
447 "string longer than given size");
448 luaL_addlstring_53(b, s, len); /* add string */
449 while (len++ < (size_t)size) /* pad extra space */
450 luaL_addchar_53(b, LUAL_PACKPADBYTE);
451 break;
452 }
453 case Kstring: { /* strings with length count */
454 size_t len;
455 const char *s = luaL_checklstring(L, arg, &len);
456 luaL_argcheck(L, size >= (int)sizeof(size_t) ||
457 len < ((size_t)1 << (size * NB)),
458 arg, "string length does not fit in given size");
459 packint(b, (lua_Unsigned)len, h.islittle, size, 0); /* pack length */
460 luaL_addlstring_53(b, s, len);
461 totalsize += len;
462 break;
463 }
464 case Kzstr: { /* zero-terminated string */
465 size_t len;
466 const char *s = luaL_checklstring(L, arg, &len);
467 luaL_argcheck(L, strlen(s) == len, arg, "string contains zeros");
468 luaL_addlstring_53(b, s, len);
469 luaL_addchar_53(b, '\0'); /* add zero at the end */
470 totalsize += len + 1;
471 break;
472 }
473 case Kpadding: luaL_addchar_53(b, LUAL_PACKPADBYTE); /* FALLTHROUGH */
474 case Kpaddalign: case Knop:
475 arg--; /* undo increment */
476 break;
477 }
478 }
479}
480
481
482int lua53_str_packsize (lua_State *L) {
483 Header h;
484 const char *fmt = luaL_checkstring(L, 1); /* format string */
485 size_t totalsize = 0; /* accumulate total size of result */
486 initheader(L, &h);
487 while (*fmt != '\0') {
488 int size, ntoalign;
489 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign);
490 size += ntoalign; /* total space used by option */
491 luaL_argcheck(L, totalsize <= MAXSIZE - size, 1,
492 "format result too large");
493 totalsize += size;
494 switch (opt) {
495 case Kstring: /* strings with length count */
496 case Kzstr: /* zero-terminated string */
497 luaL_argerror(L, 1, "variable-length format");
498 /* call never return, but to avoid warnings: *//* FALLTHROUGH */
499 default: break;
500 }
501 }
502 lua_pushinteger(L, (lua_Integer)totalsize);
503 return 1;
504}
505
506
507/*
508** Unpack an integer with 'size' bytes and 'islittle' endianness.
509** If size is smaller than the size of a Lua integer and integer
510** is signed, must do sign extension (propagating the sign to the
511** higher bits); if size is larger than the size of a Lua integer,
512** it must check the unread bytes to see whether they do not cause an
513** overflow.
514*/
515static lua_Integer unpackint (lua_State *L, const char *str,
516 int islittle, int size, int issigned) {
517 lua_Unsigned res = 0;
518 int i;
519 int limit = (size <= SZINT) ? size : SZINT;
520 for (i = limit - 1; i >= 0; i--) {
521 res <<= NB;
522 res |= (lua_Unsigned)(unsigned char)str[islittle ? i : size - 1 - i];
523 }
524 if (size < SZINT) { /* real size smaller than lua_Integer? */
525 if (issigned) { /* needs sign extension? */
526 lua_Unsigned mask = (lua_Unsigned)1 << (size*NB - 1);
527 res = ((res ^ mask) - mask); /* do sign extension */
528 }
529 }
530 else if (size > SZINT) { /* must check unread bytes */
531 int mask = (!issigned || (lua_Integer)res >= 0) ? 0 : MC;
532 for (i = limit; i < size; i++) {
533 if ((unsigned char)str[islittle ? i : size - 1 - i] != mask)
534 luaL_error(L, "%d-byte integer does not fit into Lua Integer", size);
535 }
536 }
537 return (lua_Integer)res;
538}
539
540
541int lua53_str_unpack (lua_State *L, const char *fmt, const char *data, size_t ld, int dataidx, int posidx) {
542 Header h;
543 size_t pos = (size_t)posrelat(luaL_optinteger(L, posidx, 1), ld) - 1;
544 int n = 0; /* number of results */
545 luaL_argcheck(L, pos <= ld, posidx, "initial position out of string");
546 initheader(L, &h);
547 while (*fmt != '\0') {
548 int size, ntoalign;
549 KOption opt = getdetails(&h, pos, &fmt, &size, &ntoalign);
550 if ((size_t)ntoalign + size > ~pos || pos + ntoalign + size > ld)
551 luaL_argerror(L, dataidx, "data string too short");
552 pos += ntoalign; /* skip alignment */
553 /* stack space for item + next position */
554 luaL_checkstack(L, dataidx, "too many results");
555 n++;
556 switch (opt) {
557 case Kint:
558 case Kuint: {
559 lua_Integer res = unpackint(L, data + pos, h.islittle, size,
560 (opt == Kint));
561 lua_pushinteger(L, res);
562 break;
563 }
564 case Kfloat: {
565 volatile Ftypes u;
566 lua_Number num;
567 copywithendian(u.buff, data + pos, size, h.islittle);
568 if (size == sizeof(u.f)) num = (lua_Number)u.f;
569 else if (size == sizeof(u.d)) num = (lua_Number)u.d;
570 else num = u.n;
571 lua_pushnumber(L, num);
572 break;
573 }
574 case Kchar: {
575 lua_pushlstring(L, data + pos, size);
576 break;
577 }
578 case Kstring: {
579 size_t len = (size_t)unpackint(L, data + pos, h.islittle, size, 0);
580 luaL_argcheck(L, pos + len + size <= ld, dataidx, "data string too short");
581 lua_pushlstring(L, data + pos + size, len);
582 pos += len; /* skip string */
583 break;
584 }
585 case Kzstr: {
586 size_t len = (int)strlen(data + pos);
587 lua_pushlstring(L, data + pos, len);
588 pos += len + 1; /* skip string plus final '\0' */
589 break;
590 }
591 case Kpaddalign: case Kpadding: case Knop:
592 n--; /* undo increment */
593 break;
594 }
595 pos += size;
596 }
597 lua_pushinteger(L, pos + 1); /* next position */
598 return n + 1;
599}
600
601/* }====================================================== */
602
603