mudgangster

Tiny, scriptable MUD client
Log | Files | Refs | README

lstrlib.cc (47175B)


      1 /*
      2 ** $Id: lstrlib.c,v 1.254.1.1 2017/04/19 17:29:57 roberto Exp $
      3 ** Standard library for string operations and pattern-matching
      4 ** See Copyright Notice in lua.h
      5 */
      6 
      7 #define lstrlib_c
      8 #define LUA_LIB
      9 
     10 #include "lprefix.h"
     11 
     12 
     13 #include <ctype.h>
     14 #include <float.h>
     15 #include <limits.h>
     16 #include <locale.h>
     17 #include <stddef.h>
     18 #include <stdio.h>
     19 #include <stdlib.h>
     20 #include <string.h>
     21 
     22 #include "lua.h"
     23 
     24 #include "lauxlib.h"
     25 #include "lualib.h"
     26 
     27 
     28 /*
     29 ** maximum number of captures that a pattern can do during
     30 ** pattern-matching. This limit is arbitrary, but must fit in
     31 ** an unsigned char.
     32 */
     33 #if !defined(LUA_MAXCAPTURES)
     34 #define LUA_MAXCAPTURES		32
     35 #endif
     36 
     37 
     38 /* macro to 'unsign' a character */
     39 #define uchar(c)	((unsigned char)(c))
     40 
     41 
     42 /*
     43 ** Some sizes are better limited to fit in 'int', but must also fit in
     44 ** 'size_t'. (We assume that 'lua_Integer' cannot be smaller than 'int'.)
     45 */
     46 #define MAX_SIZET	((size_t)(~(size_t)0))
     47 
     48 #define MAXSIZE  \
     49 	(sizeof(size_t) < sizeof(int) ? MAX_SIZET : (size_t)(INT_MAX))
     50 
     51 
     52 
     53 
     54 static int str_len (lua_State *L) {
     55   size_t l;
     56   luaL_checklstring(L, 1, &l);
     57   lua_pushinteger(L, (lua_Integer)l);
     58   return 1;
     59 }
     60 
     61 
     62 /* translate a relative string position: negative means back from end */
     63 static lua_Integer posrelat (lua_Integer pos, size_t len) {
     64   if (pos >= 0) return pos;
     65   else if (0u - (size_t)pos > len) return 0;
     66   else return (lua_Integer)len + pos + 1;
     67 }
     68 
     69 
     70 static int str_sub (lua_State *L) {
     71   size_t l;
     72   const char *s = luaL_checklstring(L, 1, &l);
     73   lua_Integer start = posrelat(luaL_checkinteger(L, 2), l);
     74   lua_Integer end = posrelat(luaL_optinteger(L, 3, -1), l);
     75   if (start < 1) start = 1;
     76   if (end > (lua_Integer)l) end = l;
     77   if (start <= end)
     78     lua_pushlstring(L, s + start - 1, (size_t)(end - start) + 1);
     79   else lua_pushliteral(L, "");
     80   return 1;
     81 }
     82 
     83 
     84 static int str_reverse (lua_State *L) {
     85   size_t l, i;
     86   luaL_Buffer b;
     87   const char *s = luaL_checklstring(L, 1, &l);
     88   char *p = luaL_buffinitsize(L, &b, l);
     89   for (i = 0; i < l; i++)
     90     p[i] = s[l - i - 1];
     91   luaL_pushresultsize(&b, l);
     92   return 1;
     93 }
     94 
     95 
     96 static int str_lower (lua_State *L) {
     97   size_t l;
     98   size_t i;
     99   luaL_Buffer b;
    100   const char *s = luaL_checklstring(L, 1, &l);
    101   char *p = luaL_buffinitsize(L, &b, l);
    102   for (i=0; i<l; i++)
    103     p[i] = tolower(uchar(s[i]));
    104   luaL_pushresultsize(&b, l);
    105   return 1;
    106 }
    107 
    108 
    109 static int str_upper (lua_State *L) {
    110   size_t l;
    111   size_t i;
    112   luaL_Buffer b;
    113   const char *s = luaL_checklstring(L, 1, &l);
    114   char *p = luaL_buffinitsize(L, &b, l);
    115   for (i=0; i<l; i++)
    116     p[i] = toupper(uchar(s[i]));
    117   luaL_pushresultsize(&b, l);
    118   return 1;
    119 }
    120 
    121 
    122 static int str_rep (lua_State *L) {
    123   size_t l, lsep;
    124   const char *s = luaL_checklstring(L, 1, &l);
    125   lua_Integer n = luaL_checkinteger(L, 2);
    126   const char *sep = luaL_optlstring(L, 3, "", &lsep);
    127   if (n <= 0) lua_pushliteral(L, "");
    128   else if (l + lsep < l || l + lsep > MAXSIZE / n)  /* may overflow? */
    129     return luaL_error(L, "resulting string too large");
    130   else {
    131     size_t totallen = (size_t)n * l + (size_t)(n - 1) * lsep;
    132     luaL_Buffer b;
    133     char *p = luaL_buffinitsize(L, &b, totallen);
    134     while (n-- > 1) {  /* first n-1 copies (followed by separator) */
    135       memcpy(p, s, l * sizeof(char)); p += l;
    136       if (lsep > 0) {  /* empty 'memcpy' is not that cheap */
    137         memcpy(p, sep, lsep * sizeof(char));
    138         p += lsep;
    139       }
    140     }
    141     memcpy(p, s, l * sizeof(char));  /* last copy (not followed by separator) */
    142     luaL_pushresultsize(&b, totallen);
    143   }
    144   return 1;
    145 }
    146 
    147 
    148 static int str_byte (lua_State *L) {
    149   size_t l;
    150   const char *s = luaL_checklstring(L, 1, &l);
    151   lua_Integer posi = posrelat(luaL_optinteger(L, 2, 1), l);
    152   lua_Integer pose = posrelat(luaL_optinteger(L, 3, posi), l);
    153   int n, i;
    154   if (posi < 1) posi = 1;
    155   if (pose > (lua_Integer)l) pose = l;
    156   if (posi > pose) return 0;  /* empty interval; return no values */
    157   if (pose - posi >= INT_MAX)  /* arithmetic overflow? */
    158     return luaL_error(L, "string slice too long");
    159   n = (int)(pose -  posi) + 1;
    160   luaL_checkstack(L, n, "string slice too long");
    161   for (i=0; i<n; i++)
    162     lua_pushinteger(L, uchar(s[posi+i-1]));
    163   return n;
    164 }
    165 
    166 
    167 static int str_char (lua_State *L) {
    168   int n = lua_gettop(L);  /* number of arguments */
    169   int i;
    170   luaL_Buffer b;
    171   char *p = luaL_buffinitsize(L, &b, n);
    172   for (i=1; i<=n; i++) {
    173     lua_Integer c = luaL_checkinteger(L, i);
    174     luaL_argcheck(L, uchar(c) == c, i, "value out of range");
    175     p[i - 1] = uchar(c);
    176   }
    177   luaL_pushresultsize(&b, n);
    178   return 1;
    179 }
    180 
    181 
    182 static int writer (lua_State *L, const void *b, size_t size, void *B) {
    183   (void)L;
    184   luaL_addlstring((luaL_Buffer *) B, (const char *)b, size);
    185   return 0;
    186 }
    187 
    188 
    189 static int str_dump (lua_State *L) {
    190   luaL_Buffer b;
    191   int strip = lua_toboolean(L, 2);
    192   luaL_checktype(L, 1, LUA_TFUNCTION);
    193   lua_settop(L, 1);
    194   luaL_buffinit(L,&b);
    195   if (lua_dump(L, writer, &b, strip) != 0)
    196     return luaL_error(L, "unable to dump given function");
    197   luaL_pushresult(&b);
    198   return 1;
    199 }
    200 
    201 
    202 
    203 /*
    204 ** {======================================================
    205 ** PATTERN MATCHING
    206 ** =======================================================
    207 */
    208 
    209 
    210 #define CAP_UNFINISHED	(-1)
    211 #define CAP_POSITION	(-2)
    212 
    213 
    214 typedef struct MatchState {
    215   const char *src_init;  /* init of source string */
    216   const char *src_end;  /* end ('\0') of source string */
    217   const char *p_end;  /* end ('\0') of pattern */
    218   lua_State *L;
    219   int matchdepth;  /* control for recursive depth (to avoid C stack overflow) */
    220   unsigned char level;  /* total number of captures (finished or unfinished) */
    221   struct {
    222     const char *init;
    223     ptrdiff_t len;
    224   } capture[LUA_MAXCAPTURES];
    225 } MatchState;
    226 
    227 
    228 /* recursive function */
    229 static const char *match (MatchState *ms, const char *s, const char *p);
    230 
    231 
    232 /* maximum recursion depth for 'match' */
    233 #if !defined(MAXCCALLS)
    234 #define MAXCCALLS	200
    235 #endif
    236 
    237 
    238 #define L_ESC		'%'
    239 #define SPECIALS	"^$*+?.([%-"
    240 
    241 
    242 static int check_capture (MatchState *ms, int l) {
    243   l -= '1';
    244   if (l < 0 || l >= ms->level || ms->capture[l].len == CAP_UNFINISHED)
    245     return luaL_error(ms->L, "invalid capture index %%%d", l + 1);
    246   return l;
    247 }
    248 
    249 
    250 static int capture_to_close (MatchState *ms) {
    251   int level = ms->level;
    252   for (level--; level>=0; level--)
    253     if (ms->capture[level].len == CAP_UNFINISHED) return level;
    254   return luaL_error(ms->L, "invalid pattern capture");
    255 }
    256 
    257 
    258 static const char *classend (MatchState *ms, const char *p) {
    259   switch (*p++) {
    260     case L_ESC: {
    261       if (p == ms->p_end)
    262         luaL_error(ms->L, "malformed pattern (ends with '%%')");
    263       return p+1;
    264     }
    265     case '[': {
    266       if (*p == '^') p++;
    267       do {  /* look for a ']' */
    268         if (p == ms->p_end)
    269           luaL_error(ms->L, "malformed pattern (missing ']')");
    270         if (*(p++) == L_ESC && p < ms->p_end)
    271           p++;  /* skip escapes (e.g. '%]') */
    272       } while (*p != ']');
    273       return p+1;
    274     }
    275     default: {
    276       return p;
    277     }
    278   }
    279 }
    280 
    281 
    282 static int match_class (int c, int cl) {
    283   int res;
    284   switch (tolower(cl)) {
    285     case 'a' : res = isalpha(c); break;
    286     case 'c' : res = iscntrl(c); break;
    287     case 'd' : res = isdigit(c); break;
    288     case 'g' : res = isgraph(c); break;
    289     case 'l' : res = islower(c); break;
    290     case 'p' : res = ispunct(c); break;
    291     case 's' : res = isspace(c); break;
    292     case 'u' : res = isupper(c); break;
    293     case 'w' : res = isalnum(c); break;
    294     case 'x' : res = isxdigit(c); break;
    295     case 'z' : res = (c == 0); break;  /* deprecated option */
    296     default: return (cl == c);
    297   }
    298   return (islower(cl) ? res : !res);
    299 }
    300 
    301 
    302 static int matchbracketclass (int c, const char *p, const char *ec) {
    303   int sig = 1;
    304   if (*(p+1) == '^') {
    305     sig = 0;
    306     p++;  /* skip the '^' */
    307   }
    308   while (++p < ec) {
    309     if (*p == L_ESC) {
    310       p++;
    311       if (match_class(c, uchar(*p)))
    312         return sig;
    313     }
    314     else if ((*(p+1) == '-') && (p+2 < ec)) {
    315       p+=2;
    316       if (uchar(*(p-2)) <= c && c <= uchar(*p))
    317         return sig;
    318     }
    319     else if (uchar(*p) == c) return sig;
    320   }
    321   return !sig;
    322 }
    323 
    324 
    325 static int singlematch (MatchState *ms, const char *s, const char *p,
    326                         const char *ep) {
    327   if (s >= ms->src_end)
    328     return 0;
    329   else {
    330     int c = uchar(*s);
    331     switch (*p) {
    332       case '.': return 1;  /* matches any char */
    333       case L_ESC: return match_class(c, uchar(*(p+1)));
    334       case '[': return matchbracketclass(c, p, ep-1);
    335       default:  return (uchar(*p) == c);
    336     }
    337   }
    338 }
    339 
    340 
    341 static const char *matchbalance (MatchState *ms, const char *s,
    342                                    const char *p) {
    343   if (p >= ms->p_end - 1)
    344     luaL_error(ms->L, "malformed pattern (missing arguments to '%%b')");
    345   if (*s != *p) return NULL;
    346   else {
    347     int b = *p;
    348     int e = *(p+1);
    349     int cont = 1;
    350     while (++s < ms->src_end) {
    351       if (*s == e) {
    352         if (--cont == 0) return s+1;
    353       }
    354       else if (*s == b) cont++;
    355     }
    356   }
    357   return NULL;  /* string ends out of balance */
    358 }
    359 
    360 
    361 static const char *max_expand (MatchState *ms, const char *s,
    362                                  const char *p, const char *ep) {
    363   ptrdiff_t i = 0;  /* counts maximum expand for item */
    364   while (singlematch(ms, s + i, p, ep))
    365     i++;
    366   /* keeps trying to match with the maximum repetitions */
    367   while (i>=0) {
    368     const char *res = match(ms, (s+i), ep+1);
    369     if (res) return res;
    370     i--;  /* else didn't match; reduce 1 repetition to try again */
    371   }
    372   return NULL;
    373 }
    374 
    375 
    376 static const char *min_expand (MatchState *ms, const char *s,
    377                                  const char *p, const char *ep) {
    378   for (;;) {
    379     const char *res = match(ms, s, ep+1);
    380     if (res != NULL)
    381       return res;
    382     else if (singlematch(ms, s, p, ep))
    383       s++;  /* try with one more repetition */
    384     else return NULL;
    385   }
    386 }
    387 
    388 
    389 static const char *start_capture (MatchState *ms, const char *s,
    390                                     const char *p, int what) {
    391   const char *res;
    392   int level = ms->level;
    393   if (level >= LUA_MAXCAPTURES) luaL_error(ms->L, "too many captures");
    394   ms->capture[level].init = s;
    395   ms->capture[level].len = what;
    396   ms->level = level+1;
    397   if ((res=match(ms, s, p)) == NULL)  /* match failed? */
    398     ms->level--;  /* undo capture */
    399   return res;
    400 }
    401 
    402 
    403 static const char *end_capture (MatchState *ms, const char *s,
    404                                   const char *p) {
    405   int l = capture_to_close(ms);
    406   const char *res;
    407   ms->capture[l].len = s - ms->capture[l].init;  /* close capture */
    408   if ((res = match(ms, s, p)) == NULL)  /* match failed? */
    409     ms->capture[l].len = CAP_UNFINISHED;  /* undo capture */
    410   return res;
    411 }
    412 
    413 
    414 static const char *match_capture (MatchState *ms, const char *s, int l) {
    415   size_t len;
    416   l = check_capture(ms, l);
    417   len = ms->capture[l].len;
    418   if ((size_t)(ms->src_end-s) >= len &&
    419       memcmp(ms->capture[l].init, s, len) == 0)
    420     return s+len;
    421   else return NULL;
    422 }
    423 
    424 
    425 static const char *match (MatchState *ms, const char *s, const char *p) {
    426   if (ms->matchdepth-- == 0)
    427     luaL_error(ms->L, "pattern too complex");
    428   init: /* using goto's to optimize tail recursion */
    429   if (p != ms->p_end) {  /* end of pattern? */
    430     switch (*p) {
    431       case '(': {  /* start capture */
    432         if (*(p + 1) == ')')  /* position capture? */
    433           s = start_capture(ms, s, p + 2, CAP_POSITION);
    434         else
    435           s = start_capture(ms, s, p + 1, CAP_UNFINISHED);
    436         break;
    437       }
    438       case ')': {  /* end capture */
    439         s = end_capture(ms, s, p + 1);
    440         break;
    441       }
    442       case '$': {
    443         if ((p + 1) != ms->p_end)  /* is the '$' the last char in pattern? */
    444           goto dflt;  /* no; go to default */
    445         s = (s == ms->src_end) ? s : NULL;  /* check end of string */
    446         break;
    447       }
    448       case L_ESC: {  /* escaped sequences not in the format class[*+?-]? */
    449         switch (*(p + 1)) {
    450           case 'b': {  /* balanced string? */
    451             s = matchbalance(ms, s, p + 2);
    452             if (s != NULL) {
    453               p += 4; goto init;  /* return match(ms, s, p + 4); */
    454             }  /* else fail (s == NULL) */
    455             break;
    456           }
    457           case 'f': {  /* frontier? */
    458             const char *ep; char previous;
    459             p += 2;
    460             if (*p != '[')
    461               luaL_error(ms->L, "missing '[' after '%%f' in pattern");
    462             ep = classend(ms, p);  /* points to what is next */
    463             previous = (s == ms->src_init) ? '\0' : *(s - 1);
    464             if (!matchbracketclass(uchar(previous), p, ep - 1) &&
    465                matchbracketclass(uchar(*s), p, ep - 1)) {
    466               p = ep; goto init;  /* return match(ms, s, ep); */
    467             }
    468             s = NULL;  /* match failed */
    469             break;
    470           }
    471           case '0': case '1': case '2': case '3':
    472           case '4': case '5': case '6': case '7':
    473           case '8': case '9': {  /* capture results (%0-%9)? */
    474             s = match_capture(ms, s, uchar(*(p + 1)));
    475             if (s != NULL) {
    476               p += 2; goto init;  /* return match(ms, s, p + 2) */
    477             }
    478             break;
    479           }
    480           default: goto dflt;
    481         }
    482         break;
    483       }
    484       default: dflt: {  /* pattern class plus optional suffix */
    485         const char *ep = classend(ms, p);  /* points to optional suffix */
    486         /* does not match at least once? */
    487         if (!singlematch(ms, s, p, ep)) {
    488           if (*ep == '*' || *ep == '?' || *ep == '-') {  /* accept empty? */
    489             p = ep + 1; goto init;  /* return match(ms, s, ep + 1); */
    490           }
    491           else  /* '+' or no suffix */
    492             s = NULL;  /* fail */
    493         }
    494         else {  /* matched once */
    495           switch (*ep) {  /* handle optional suffix */
    496             case '?': {  /* optional */
    497               const char *res;
    498               if ((res = match(ms, s + 1, ep + 1)) != NULL)
    499                 s = res;
    500               else {
    501                 p = ep + 1; goto init;  /* else return match(ms, s, ep + 1); */
    502               }
    503               break;
    504             }
    505             case '+':  /* 1 or more repetitions */
    506               s++;  /* 1 match already done */
    507               /* FALLTHROUGH */
    508             case '*':  /* 0 or more repetitions */
    509               s = max_expand(ms, s, p, ep);
    510               break;
    511             case '-':  /* 0 or more repetitions (minimum) */
    512               s = min_expand(ms, s, p, ep);
    513               break;
    514             default:  /* no suffix */
    515               s++; p = ep; goto init;  /* return match(ms, s + 1, ep); */
    516           }
    517         }
    518         break;
    519       }
    520     }
    521   }
    522   ms->matchdepth++;
    523   return s;
    524 }
    525 
    526 
    527 
    528 static const char *lmemfind (const char *s1, size_t l1,
    529                                const char *s2, size_t l2) {
    530   if (l2 == 0) return s1;  /* empty strings are everywhere */
    531   else if (l2 > l1) return NULL;  /* avoids a negative 'l1' */
    532   else {
    533     const char *init;  /* to search for a '*s2' inside 's1' */
    534     l2--;  /* 1st char will be checked by 'memchr' */
    535     l1 = l1-l2;  /* 's2' cannot be found after that */
    536     while (l1 > 0 && (init = (const char *)memchr(s1, *s2, l1)) != NULL) {
    537       init++;   /* 1st char is already checked */
    538       if (memcmp(init, s2+1, l2) == 0)
    539         return init-1;
    540       else {  /* correct 'l1' and 's1' to try again */
    541         l1 -= init-s1;
    542         s1 = init;
    543       }
    544     }
    545     return NULL;  /* not found */
    546   }
    547 }
    548 
    549 
    550 static void push_onecapture (MatchState *ms, int i, const char *s,
    551                                                     const char *e) {
    552   if (i >= ms->level) {
    553     if (i == 0)  /* ms->level == 0, too */
    554       lua_pushlstring(ms->L, s, e - s);  /* add whole match */
    555     else
    556       luaL_error(ms->L, "invalid capture index %%%d", i + 1);
    557   }
    558   else {
    559     ptrdiff_t l = ms->capture[i].len;
    560     if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture");
    561     if (l == CAP_POSITION)
    562       lua_pushinteger(ms->L, (ms->capture[i].init - ms->src_init) + 1);
    563     else
    564       lua_pushlstring(ms->L, ms->capture[i].init, l);
    565   }
    566 }
    567 
    568 
    569 static int push_captures (MatchState *ms, const char *s, const char *e) {
    570   int i;
    571   int nlevels = (ms->level == 0 && s) ? 1 : ms->level;
    572   luaL_checkstack(ms->L, nlevels, "too many captures");
    573   for (i = 0; i < nlevels; i++)
    574     push_onecapture(ms, i, s, e);
    575   return nlevels;  /* number of strings pushed */
    576 }
    577 
    578 
    579 /* check whether pattern has no special characters */
    580 static int nospecials (const char *p, size_t l) {
    581   size_t upto = 0;
    582   do {
    583     if (strpbrk(p + upto, SPECIALS))
    584       return 0;  /* pattern has a special character */
    585     upto += strlen(p + upto) + 1;  /* may have more after \0 */
    586   } while (upto <= l);
    587   return 1;  /* no special chars found */
    588 }
    589 
    590 
    591 static void prepstate (MatchState *ms, lua_State *L,
    592                        const char *s, size_t ls, const char *p, size_t lp) {
    593   ms->L = L;
    594   ms->matchdepth = MAXCCALLS;
    595   ms->src_init = s;
    596   ms->src_end = s + ls;
    597   ms->p_end = p + lp;
    598 }
    599 
    600 
    601 static void reprepstate (MatchState *ms) {
    602   ms->level = 0;
    603   lua_assert(ms->matchdepth == MAXCCALLS);
    604 }
    605 
    606 
    607 static int str_find_aux (lua_State *L, int find) {
    608   size_t ls, lp;
    609   const char *s = luaL_checklstring(L, 1, &ls);
    610   const char *p = luaL_checklstring(L, 2, &lp);
    611   lua_Integer init = posrelat(luaL_optinteger(L, 3, 1), ls);
    612   if (init < 1) init = 1;
    613   else if (init > (lua_Integer)ls + 1) {  /* start after string's end? */
    614     lua_pushnil(L);  /* cannot find anything */
    615     return 1;
    616   }
    617   /* explicit request or no special characters? */
    618   if (find && (lua_toboolean(L, 4) || nospecials(p, lp))) {
    619     /* do a plain search */
    620     const char *s2 = lmemfind(s + init - 1, ls - (size_t)init + 1, p, lp);
    621     if (s2) {
    622       lua_pushinteger(L, (s2 - s) + 1);
    623       lua_pushinteger(L, (s2 - s) + lp);
    624       return 2;
    625     }
    626   }
    627   else {
    628     MatchState ms;
    629     const char *s1 = s + init - 1;
    630     int anchor = (*p == '^');
    631     if (anchor) {
    632       p++; lp--;  /* skip anchor character */
    633     }
    634     prepstate(&ms, L, s, ls, p, lp);
    635     do {
    636       const char *res;
    637       reprepstate(&ms);
    638       if ((res=match(&ms, s1, p)) != NULL) {
    639         if (find) {
    640           lua_pushinteger(L, (s1 - s) + 1);  /* start */
    641           lua_pushinteger(L, res - s);   /* end */
    642           return push_captures(&ms, NULL, 0) + 2;
    643         }
    644         else
    645           return push_captures(&ms, s1, res);
    646       }
    647     } while (s1++ < ms.src_end && !anchor);
    648   }
    649   lua_pushnil(L);  /* not found */
    650   return 1;
    651 }
    652 
    653 
    654 static int str_find (lua_State *L) {
    655   return str_find_aux(L, 1);
    656 }
    657 
    658 
    659 static int str_match (lua_State *L) {
    660   return str_find_aux(L, 0);
    661 }
    662 
    663 
    664 /* state for 'gmatch' */
    665 typedef struct GMatchState {
    666   const char *src;  /* current position */
    667   const char *p;  /* pattern */
    668   const char *lastmatch;  /* end of last match */
    669   MatchState ms;  /* match state */
    670 } GMatchState;
    671 
    672 
    673 static int gmatch_aux (lua_State *L) {
    674   GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3));
    675   const char *src;
    676   gm->ms.L = L;
    677   for (src = gm->src; src <= gm->ms.src_end; src++) {
    678     const char *e;
    679     reprepstate(&gm->ms);
    680     if ((e = match(&gm->ms, src, gm->p)) != NULL && e != gm->lastmatch) {
    681       gm->src = gm->lastmatch = e;
    682       return push_captures(&gm->ms, src, e);
    683     }
    684   }
    685   return 0;  /* not found */
    686 }
    687 
    688 
    689 static int gmatch (lua_State *L) {
    690   size_t ls, lp;
    691   const char *s = luaL_checklstring(L, 1, &ls);
    692   const char *p = luaL_checklstring(L, 2, &lp);
    693   GMatchState *gm;
    694   lua_settop(L, 2);  /* keep them on closure to avoid being collected */
    695   gm = (GMatchState *)lua_newuserdata(L, sizeof(GMatchState));
    696   prepstate(&gm->ms, L, s, ls, p, lp);
    697   gm->src = s; gm->p = p; gm->lastmatch = NULL;
    698   lua_pushcclosure(L, gmatch_aux, 3);
    699   return 1;
    700 }
    701 
    702 
    703 static void add_s (MatchState *ms, luaL_Buffer *b, const char *s,
    704                                                    const char *e) {
    705   size_t l, i;
    706   lua_State *L = ms->L;
    707   const char *news = lua_tolstring(L, 3, &l);
    708   for (i = 0; i < l; i++) {
    709     if (news[i] != L_ESC)
    710       luaL_addchar(b, news[i]);
    711     else {
    712       i++;  /* skip ESC */
    713       if (!isdigit(uchar(news[i]))) {
    714         if (news[i] != L_ESC)
    715           luaL_error(L, "invalid use of '%c' in replacement string", L_ESC);
    716         luaL_addchar(b, news[i]);
    717       }
    718       else if (news[i] == '0')
    719           luaL_addlstring(b, s, e - s);
    720       else {
    721         push_onecapture(ms, news[i] - '1', s, e);
    722         luaL_tolstring(L, -1, NULL);  /* if number, convert it to string */
    723         lua_remove(L, -2);  /* remove original value */
    724         luaL_addvalue(b);  /* add capture to accumulated result */
    725       }
    726     }
    727   }
    728 }
    729 
    730 
    731 static void add_value (MatchState *ms, luaL_Buffer *b, const char *s,
    732                                        const char *e, int tr) {
    733   lua_State *L = ms->L;
    734   switch (tr) {
    735     case LUA_TFUNCTION: {
    736       int n;
    737       lua_pushvalue(L, 3);
    738       n = push_captures(ms, s, e);
    739       lua_call(L, n, 1);
    740       break;
    741     }
    742     case LUA_TTABLE: {
    743       push_onecapture(ms, 0, s, e);
    744       lua_gettable(L, 3);
    745       break;
    746     }
    747     default: {  /* LUA_TNUMBER or LUA_TSTRING */
    748       add_s(ms, b, s, e);
    749       return;
    750     }
    751   }
    752   if (!lua_toboolean(L, -1)) {  /* nil or false? */
    753     lua_pop(L, 1);
    754     lua_pushlstring(L, s, e - s);  /* keep original text */
    755   }
    756   else if (!lua_isstring(L, -1))
    757     luaL_error(L, "invalid replacement value (a %s)", luaL_typename(L, -1));
    758   luaL_addvalue(b);  /* add result to accumulator */
    759 }
    760 
    761 
    762 static int str_gsub (lua_State *L) {
    763   size_t srcl, lp;
    764   const char *src = luaL_checklstring(L, 1, &srcl);  /* subject */
    765   const char *p = luaL_checklstring(L, 2, &lp);  /* pattern */
    766   const char *lastmatch = NULL;  /* end of last match */
    767   int tr = lua_type(L, 3);  /* replacement type */
    768   lua_Integer max_s = luaL_optinteger(L, 4, srcl + 1);  /* max replacements */
    769   int anchor = (*p == '^');
    770   lua_Integer n = 0;  /* replacement count */
    771   MatchState ms;
    772   luaL_Buffer b;
    773   luaL_argcheck(L, tr == LUA_TNUMBER || tr == LUA_TSTRING ||
    774                    tr == LUA_TFUNCTION || tr == LUA_TTABLE, 3,
    775                       "string/function/table expected");
    776   luaL_buffinit(L, &b);
    777   if (anchor) {
    778     p++; lp--;  /* skip anchor character */
    779   }
    780   prepstate(&ms, L, src, srcl, p, lp);
    781   while (n < max_s) {
    782     const char *e;
    783     reprepstate(&ms);  /* (re)prepare state for new match */
    784     if ((e = match(&ms, src, p)) != NULL && e != lastmatch) {  /* match? */
    785       n++;
    786       add_value(&ms, &b, src, e, tr);  /* add replacement to buffer */
    787       src = lastmatch = e;
    788     }
    789     else if (src < ms.src_end)  /* otherwise, skip one character */
    790       luaL_addchar(&b, *src++);
    791     else break;  /* end of subject */
    792     if (anchor) break;
    793   }
    794   luaL_addlstring(&b, src, ms.src_end-src);
    795   luaL_pushresult(&b);
    796   lua_pushinteger(L, n);  /* number of substitutions */
    797   return 2;
    798 }
    799 
    800 /* }====================================================== */
    801 
    802 
    803 
    804 /*
    805 ** {======================================================
    806 ** STRING FORMAT
    807 ** =======================================================
    808 */
    809 
    810 #if !defined(lua_number2strx)	/* { */
    811 
    812 /*
    813 ** Hexadecimal floating-point formatter
    814 */
    815 
    816 #include <math.h>
    817 
    818 #define SIZELENMOD	(sizeof(LUA_NUMBER_FRMLEN)/sizeof(char))
    819 
    820 
    821 /*
    822 ** Number of bits that goes into the first digit. It can be any value
    823 ** between 1 and 4; the following definition tries to align the number
    824 ** to nibble boundaries by making what is left after that first digit a
    825 ** multiple of 4.
    826 */
    827 #define L_NBFD		((l_mathlim(MANT_DIG) - 1)%4 + 1)
    828 
    829 
    830 /*
    831 ** Add integer part of 'x' to buffer and return new 'x'
    832 */
    833 static lua_Number adddigit (char *buff, int n, lua_Number x) {
    834   lua_Number dd = l_mathop(floor)(x);  /* get integer part from 'x' */
    835   int d = (int)dd;
    836   buff[n] = (d < 10 ? d + '0' : d - 10 + 'a');  /* add to buffer */
    837   return x - dd;  /* return what is left */
    838 }
    839 
    840 
    841 static int num2straux (char *buff, int sz, lua_Number x) {
    842   /* if 'inf' or 'NaN', format it like '%g' */
    843   if (x != x || x == (lua_Number)HUGE_VAL || x == -(lua_Number)HUGE_VAL)
    844     return l_sprintf(buff, sz, LUA_NUMBER_FMT, (LUAI_UACNUMBER)x);
    845   else if (x == 0) {  /* can be -0... */
    846     /* create "0" or "-0" followed by exponent */
    847     return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", (LUAI_UACNUMBER)x);
    848   }
    849   else {
    850     int e;
    851     lua_Number m = l_mathop(frexp)(x, &e);  /* 'x' fraction and exponent */
    852     int n = 0;  /* character count */
    853     if (m < 0) {  /* is number negative? */
    854       buff[n++] = '-';  /* add signal */
    855       m = -m;  /* make it positive */
    856     }
    857     buff[n++] = '0'; buff[n++] = 'x';  /* add "0x" */
    858     m = adddigit(buff, n++, m * (1 << L_NBFD));  /* add first digit */
    859     e -= L_NBFD;  /* this digit goes before the radix point */
    860     if (m > 0) {  /* more digits? */
    861       buff[n++] = lua_getlocaledecpoint();  /* add radix point */
    862       do {  /* add as many digits as needed */
    863         m = adddigit(buff, n++, m * 16);
    864       } while (m > 0);
    865     }
    866     n += l_sprintf(buff + n, sz - n, "p%+d", e);  /* add exponent */
    867     lua_assert(n < sz);
    868     return n;
    869   }
    870 }
    871 
    872 
    873 static int lua_number2strx (lua_State *L, char *buff, int sz,
    874                             const char *fmt, lua_Number x) {
    875   int n = num2straux(buff, sz, x);
    876   if (fmt[SIZELENMOD] == 'A') {
    877     int i;
    878     for (i = 0; i < n; i++)
    879       buff[i] = toupper(uchar(buff[i]));
    880   }
    881   else if (fmt[SIZELENMOD] != 'a')
    882     return luaL_error(L, "modifiers for format '%%a'/'%%A' not implemented");
    883   return n;
    884 }
    885 
    886 #endif				/* } */
    887 
    888 
    889 /*
    890 ** Maximum size of each formatted item. This maximum size is produced
    891 ** by format('%.99f', -maxfloat), and is equal to 99 + 3 ('-', '.',
    892 ** and '\0') + number of decimal digits to represent maxfloat (which
    893 ** is maximum exponent + 1). (99+3+1 then rounded to 120 for "extra
    894 ** expenses", such as locale-dependent stuff)
    895 */
    896 #define MAX_ITEM        (120 + l_mathlim(MAX_10_EXP))
    897 
    898 
    899 /* valid flags in a format specification */
    900 #define FLAGS	"-+ #0"
    901 
    902 /*
    903 ** maximum size of each format specification (such as "%-099.99d")
    904 */
    905 #define MAX_FORMAT	32
    906 
    907 
    908 static void addquoted (luaL_Buffer *b, const char *s, size_t len) {
    909   luaL_addchar(b, '"');
    910   while (len--) {
    911     if (*s == '"' || *s == '\\' || *s == '\n') {
    912       luaL_addchar(b, '\\');
    913       luaL_addchar(b, *s);
    914     }
    915     else if (iscntrl(uchar(*s))) {
    916       char buff[10];
    917       if (!isdigit(uchar(*(s+1))))
    918         l_sprintf(buff, sizeof(buff), "\\%d", (int)uchar(*s));
    919       else
    920         l_sprintf(buff, sizeof(buff), "\\%03d", (int)uchar(*s));
    921       luaL_addstring(b, buff);
    922     }
    923     else
    924       luaL_addchar(b, *s);
    925     s++;
    926   }
    927   luaL_addchar(b, '"');
    928 }
    929 
    930 
    931 /*
    932 ** Ensures the 'buff' string uses a dot as the radix character.
    933 */
    934 static void checkdp (char *buff, int nb) {
    935   if (memchr(buff, '.', nb) == NULL) {  /* no dot? */
    936     char point = lua_getlocaledecpoint();  /* try locale point */
    937     char *ppoint = (char *)memchr(buff, point, nb);
    938     if (ppoint) *ppoint = '.';  /* change it to a dot */
    939   }
    940 }
    941 
    942 
    943 static void addliteral (lua_State *L, luaL_Buffer *b, int arg) {
    944   switch (lua_type(L, arg)) {
    945     case LUA_TSTRING: {
    946       size_t len;
    947       const char *s = lua_tolstring(L, arg, &len);
    948       addquoted(b, s, len);
    949       break;
    950     }
    951     case LUA_TNUMBER: {
    952       char *buff = luaL_prepbuffsize(b, MAX_ITEM);
    953       int nb;
    954       if (!lua_isinteger(L, arg)) {  /* float? */
    955         lua_Number n = lua_tonumber(L, arg);  /* write as hexa ('%a') */
    956         nb = lua_number2strx(L, buff, MAX_ITEM, "%" LUA_NUMBER_FRMLEN "a", n);
    957         checkdp(buff, nb);  /* ensure it uses a dot */
    958       }
    959       else {  /* integers */
    960         lua_Integer n = lua_tointeger(L, arg);
    961         const char *format = (n == LUA_MININTEGER)  /* corner case? */
    962                            ? "0x%" LUA_INTEGER_FRMLEN "x"  /* use hexa */
    963                            : LUA_INTEGER_FMT;  /* else use default format */
    964         nb = l_sprintf(buff, MAX_ITEM, format, (LUAI_UACINT)n);
    965       }
    966       luaL_addsize(b, nb);
    967       break;
    968     }
    969     case LUA_TNIL: case LUA_TBOOLEAN: {
    970       luaL_tolstring(L, arg, NULL);
    971       luaL_addvalue(b);
    972       break;
    973     }
    974     default: {
    975       luaL_argerror(L, arg, "value has no literal form");
    976     }
    977   }
    978 }
    979 
    980 
    981 static const char *scanformat (lua_State *L, const char *strfrmt, char *form) {
    982   const char *p = strfrmt;
    983   while (*p != '\0' && strchr(FLAGS, *p) != NULL) p++;  /* skip flags */
    984   if ((size_t)(p - strfrmt) >= sizeof(FLAGS)/sizeof(char))
    985     luaL_error(L, "invalid format (repeated flags)");
    986   if (isdigit(uchar(*p))) p++;  /* skip width */
    987   if (isdigit(uchar(*p))) p++;  /* (2 digits at most) */
    988   if (*p == '.') {
    989     p++;
    990     if (isdigit(uchar(*p))) p++;  /* skip precision */
    991     if (isdigit(uchar(*p))) p++;  /* (2 digits at most) */
    992   }
    993   if (isdigit(uchar(*p)))
    994     luaL_error(L, "invalid format (width or precision too long)");
    995   *(form++) = '%';
    996   memcpy(form, strfrmt, ((p - strfrmt) + 1) * sizeof(char));
    997   form += (p - strfrmt) + 1;
    998   *form = '\0';
    999   return p;
   1000 }
   1001 
   1002 
   1003 /*
   1004 ** add length modifier into formats
   1005 */
   1006 static void addlenmod (char *form, const char *lenmod) {
   1007   size_t l = strlen(form);
   1008   size_t lm = strlen(lenmod);
   1009   char spec = form[l - 1];
   1010   strcpy(form + l - 1, lenmod);
   1011   form[l + lm - 1] = spec;
   1012   form[l + lm] = '\0';
   1013 }
   1014 
   1015 
   1016 static int str_format (lua_State *L) {
   1017   int top = lua_gettop(L);
   1018   int arg = 1;
   1019   size_t sfl;
   1020   const char *strfrmt = luaL_checklstring(L, arg, &sfl);
   1021   const char *strfrmt_end = strfrmt+sfl;
   1022   luaL_Buffer b;
   1023   luaL_buffinit(L, &b);
   1024   while (strfrmt < strfrmt_end) {
   1025     if (*strfrmt != L_ESC)
   1026       luaL_addchar(&b, *strfrmt++);
   1027     else if (*++strfrmt == L_ESC)
   1028       luaL_addchar(&b, *strfrmt++);  /* %% */
   1029     else { /* format item */
   1030       char form[MAX_FORMAT];  /* to store the format ('%...') */
   1031       char *buff = luaL_prepbuffsize(&b, MAX_ITEM);  /* to put formatted item */
   1032       int nb = 0;  /* number of bytes in added item */
   1033       if (++arg > top)
   1034         luaL_argerror(L, arg, "no value");
   1035       strfrmt = scanformat(L, strfrmt, form);
   1036       switch (*strfrmt++) {
   1037         case 'c': {
   1038           nb = l_sprintf(buff, MAX_ITEM, form, (int)luaL_checkinteger(L, arg));
   1039           break;
   1040         }
   1041         case 'd': case 'i':
   1042         case 'o': case 'u': case 'x': case 'X': {
   1043           lua_Integer n = luaL_checkinteger(L, arg);
   1044           addlenmod(form, LUA_INTEGER_FRMLEN);
   1045           nb = l_sprintf(buff, MAX_ITEM, form, (LUAI_UACINT)n);
   1046           break;
   1047         }
   1048         case 'a': case 'A':
   1049           addlenmod(form, LUA_NUMBER_FRMLEN);
   1050           nb = lua_number2strx(L, buff, MAX_ITEM, form,
   1051                                   luaL_checknumber(L, arg));
   1052           break;
   1053         case 'e': case 'E': case 'f':
   1054         case 'g': case 'G': {
   1055           lua_Number n = luaL_checknumber(L, arg);
   1056           addlenmod(form, LUA_NUMBER_FRMLEN);
   1057           nb = l_sprintf(buff, MAX_ITEM, form, (LUAI_UACNUMBER)n);
   1058           break;
   1059         }
   1060         case 'q': {
   1061           addliteral(L, &b, arg);
   1062           break;
   1063         }
   1064         case 's': {
   1065           size_t l;
   1066           const char *s = luaL_tolstring(L, arg, &l);
   1067           if (form[2] == '\0')  /* no modifiers? */
   1068             luaL_addvalue(&b);  /* keep entire string */
   1069           else {
   1070             luaL_argcheck(L, l == strlen(s), arg, "string contains zeros");
   1071             if (!strchr(form, '.') && l >= 100) {
   1072               /* no precision and string is too long to be formatted */
   1073               luaL_addvalue(&b);  /* keep entire string */
   1074             }
   1075             else {  /* format the string into 'buff' */
   1076               nb = l_sprintf(buff, MAX_ITEM, form, s);
   1077               lua_pop(L, 1);  /* remove result from 'luaL_tolstring' */
   1078             }
   1079           }
   1080           break;
   1081         }
   1082         default: {  /* also treat cases 'pnLlh' */
   1083           return luaL_error(L, "invalid option '%%%c' to 'format'",
   1084                                *(strfrmt - 1));
   1085         }
   1086       }
   1087       lua_assert(nb < MAX_ITEM);
   1088       luaL_addsize(&b, nb);
   1089     }
   1090   }
   1091   luaL_pushresult(&b);
   1092   return 1;
   1093 }
   1094 
   1095 /* }====================================================== */
   1096 
   1097 
   1098 /*
   1099 ** {======================================================
   1100 ** PACK/UNPACK
   1101 ** =======================================================
   1102 */
   1103 
   1104 
   1105 /* value used for padding */
   1106 #if !defined(LUAL_PACKPADBYTE)
   1107 #define LUAL_PACKPADBYTE		0x00
   1108 #endif
   1109 
   1110 /* maximum size for the binary representation of an integer */
   1111 #define MAXINTSIZE	16
   1112 
   1113 /* number of bits in a character */
   1114 #define NB	CHAR_BIT
   1115 
   1116 /* mask for one character (NB 1's) */
   1117 #define MC	((1 << NB) - 1)
   1118 
   1119 /* size of a lua_Integer */
   1120 #define SZINT	((int)sizeof(lua_Integer))
   1121 
   1122 
   1123 /* dummy union to get native endianness */
   1124 static const union {
   1125   int dummy;
   1126   char little;  /* true iff machine is little endian */
   1127 } nativeendian = {1};
   1128 
   1129 
   1130 /* dummy structure to get native alignment requirements */
   1131 struct cD {
   1132   char c;
   1133   union { double d; void *p; lua_Integer i; lua_Number n; } u;
   1134 };
   1135 
   1136 #define MAXALIGN	(offsetof(struct cD, u))
   1137 
   1138 
   1139 /*
   1140 ** Union for serializing floats
   1141 */
   1142 typedef union Ftypes {
   1143   float f;
   1144   double d;
   1145   lua_Number n;
   1146   char buff[5 * sizeof(lua_Number)];  /* enough for any float type */
   1147 } Ftypes;
   1148 
   1149 
   1150 /*
   1151 ** information to pack/unpack stuff
   1152 */
   1153 typedef struct Header {
   1154   lua_State *L;
   1155   int islittle;
   1156   int maxalign;
   1157 } Header;
   1158 
   1159 
   1160 /*
   1161 ** options for pack/unpack
   1162 */
   1163 typedef enum KOption {
   1164   Kint,		/* signed integers */
   1165   Kuint,	/* unsigned integers */
   1166   Kfloat,	/* floating-point numbers */
   1167   Kchar,	/* fixed-length strings */
   1168   Kstring,	/* strings with prefixed length */
   1169   Kzstr,	/* zero-terminated strings */
   1170   Kpadding,	/* padding */
   1171   Kpaddalign,	/* padding for alignment */
   1172   Knop		/* no-op (configuration or spaces) */
   1173 } KOption;
   1174 
   1175 
   1176 /*
   1177 ** Read an integer numeral from string 'fmt' or return 'df' if
   1178 ** there is no numeral
   1179 */
   1180 static int digit (int c) { return '0' <= c && c <= '9'; }
   1181 
   1182 static int getnum (const char **fmt, int df) {
   1183   if (!digit(**fmt))  /* no number? */
   1184     return df;  /* return default value */
   1185   else {
   1186     int a = 0;
   1187     do {
   1188       a = a*10 + (*((*fmt)++) - '0');
   1189     } while (digit(**fmt) && a <= ((int)MAXSIZE - 9)/10);
   1190     return a;
   1191   }
   1192 }
   1193 
   1194 
   1195 /*
   1196 ** Read an integer numeral and raises an error if it is larger
   1197 ** than the maximum size for integers.
   1198 */
   1199 static int getnumlimit (Header *h, const char **fmt, int df) {
   1200   int sz = getnum(fmt, df);
   1201   if (sz > MAXINTSIZE || sz <= 0)
   1202     return luaL_error(h->L, "integral size (%d) out of limits [1,%d]",
   1203                             sz, MAXINTSIZE);
   1204   return sz;
   1205 }
   1206 
   1207 
   1208 /*
   1209 ** Initialize Header
   1210 */
   1211 static void initheader (lua_State *L, Header *h) {
   1212   h->L = L;
   1213   h->islittle = nativeendian.little;
   1214   h->maxalign = 1;
   1215 }
   1216 
   1217 
   1218 /*
   1219 ** Read and classify next option. 'size' is filled with option's size.
   1220 */
   1221 static KOption getoption (Header *h, const char **fmt, int *size) {
   1222   int opt = *((*fmt)++);
   1223   *size = 0;  /* default */
   1224   switch (opt) {
   1225     case 'b': *size = sizeof(char); return Kint;
   1226     case 'B': *size = sizeof(char); return Kuint;
   1227     case 'h': *size = sizeof(short); return Kint;
   1228     case 'H': *size = sizeof(short); return Kuint;
   1229     case 'l': *size = sizeof(long); return Kint;
   1230     case 'L': *size = sizeof(long); return Kuint;
   1231     case 'j': *size = sizeof(lua_Integer); return Kint;
   1232     case 'J': *size = sizeof(lua_Integer); return Kuint;
   1233     case 'T': *size = sizeof(size_t); return Kuint;
   1234     case 'f': *size = sizeof(float); return Kfloat;
   1235     case 'd': *size = sizeof(double); return Kfloat;
   1236     case 'n': *size = sizeof(lua_Number); return Kfloat;
   1237     case 'i': *size = getnumlimit(h, fmt, sizeof(int)); return Kint;
   1238     case 'I': *size = getnumlimit(h, fmt, sizeof(int)); return Kuint;
   1239     case 's': *size = getnumlimit(h, fmt, sizeof(size_t)); return Kstring;
   1240     case 'c':
   1241       *size = getnum(fmt, -1);
   1242       if (*size == -1)
   1243         luaL_error(h->L, "missing size for format option 'c'");
   1244       return Kchar;
   1245     case 'z': return Kzstr;
   1246     case 'x': *size = 1; return Kpadding;
   1247     case 'X': return Kpaddalign;
   1248     case ' ': break;
   1249     case '<': h->islittle = 1; break;
   1250     case '>': h->islittle = 0; break;
   1251     case '=': h->islittle = nativeendian.little; break;
   1252     case '!': h->maxalign = getnumlimit(h, fmt, MAXALIGN); break;
   1253     default: luaL_error(h->L, "invalid format option '%c'", opt);
   1254   }
   1255   return Knop;
   1256 }
   1257 
   1258 
   1259 /*
   1260 ** Read, classify, and fill other details about the next option.
   1261 ** 'psize' is filled with option's size, 'notoalign' with its
   1262 ** alignment requirements.
   1263 ** Local variable 'size' gets the size to be aligned. (Kpadal option
   1264 ** always gets its full alignment, other options are limited by
   1265 ** the maximum alignment ('maxalign'). Kchar option needs no alignment
   1266 ** despite its size.
   1267 */
   1268 static KOption getdetails (Header *h, size_t totalsize,
   1269                            const char **fmt, int *psize, int *ntoalign) {
   1270   KOption opt = getoption(h, fmt, psize);
   1271   int align = *psize;  /* usually, alignment follows size */
   1272   if (opt == Kpaddalign) {  /* 'X' gets alignment from following option */
   1273     if (**fmt == '\0' || getoption(h, fmt, &align) == Kchar || align == 0)
   1274       luaL_argerror(h->L, 1, "invalid next option for option 'X'");
   1275   }
   1276   if (align <= 1 || opt == Kchar)  /* need no alignment? */
   1277     *ntoalign = 0;
   1278   else {
   1279     if (align > h->maxalign)  /* enforce maximum alignment */
   1280       align = h->maxalign;
   1281     if ((align & (align - 1)) != 0)  /* is 'align' not a power of 2? */
   1282       luaL_argerror(h->L, 1, "format asks for alignment not power of 2");
   1283     *ntoalign = (align - (int)(totalsize & (align - 1))) & (align - 1);
   1284   }
   1285   return opt;
   1286 }
   1287 
   1288 
   1289 /*
   1290 ** Pack integer 'n' with 'size' bytes and 'islittle' endianness.
   1291 ** The final 'if' handles the case when 'size' is larger than
   1292 ** the size of a Lua integer, correcting the extra sign-extension
   1293 ** bytes if necessary (by default they would be zeros).
   1294 */
   1295 static void packint (luaL_Buffer *b, lua_Unsigned n,
   1296                      int islittle, int size, int neg) {
   1297   char *buff = luaL_prepbuffsize(b, size);
   1298   int i;
   1299   buff[islittle ? 0 : size - 1] = (char)(n & MC);  /* first byte */
   1300   for (i = 1; i < size; i++) {
   1301     n >>= NB;
   1302     buff[islittle ? i : size - 1 - i] = (char)(n & MC);
   1303   }
   1304   if (neg && size > SZINT) {  /* negative number need sign extension? */
   1305     for (i = SZINT; i < size; i++)  /* correct extra bytes */
   1306       buff[islittle ? i : size - 1 - i] = (char)MC;
   1307   }
   1308   luaL_addsize(b, size);  /* add result to buffer */
   1309 }
   1310 
   1311 
   1312 /*
   1313 ** Copy 'size' bytes from 'src' to 'dest', correcting endianness if
   1314 ** given 'islittle' is different from native endianness.
   1315 */
   1316 static void copywithendian (volatile char *dest, volatile const char *src,
   1317                             int size, int islittle) {
   1318   if (islittle == nativeendian.little) {
   1319     while (size-- != 0)
   1320       *(dest++) = *(src++);
   1321   }
   1322   else {
   1323     dest += size - 1;
   1324     while (size-- != 0)
   1325       *(dest--) = *(src++);
   1326   }
   1327 }
   1328 
   1329 
   1330 static int str_pack (lua_State *L) {
   1331   luaL_Buffer b;
   1332   Header h;
   1333   const char *fmt = luaL_checkstring(L, 1);  /* format string */
   1334   int arg = 1;  /* current argument to pack */
   1335   size_t totalsize = 0;  /* accumulate total size of result */
   1336   initheader(L, &h);
   1337   lua_pushnil(L);  /* mark to separate arguments from string buffer */
   1338   luaL_buffinit(L, &b);
   1339   while (*fmt != '\0') {
   1340     int size, ntoalign;
   1341     KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign);
   1342     totalsize += ntoalign + size;
   1343     while (ntoalign-- > 0)
   1344      luaL_addchar(&b, LUAL_PACKPADBYTE);  /* fill alignment */
   1345     arg++;
   1346     switch (opt) {
   1347       case Kint: {  /* signed integers */
   1348         lua_Integer n = luaL_checkinteger(L, arg);
   1349         if (size < SZINT) {  /* need overflow check? */
   1350           lua_Integer lim = (lua_Integer)1 << ((size * NB) - 1);
   1351           luaL_argcheck(L, -lim <= n && n < lim, arg, "integer overflow");
   1352         }
   1353         packint(&b, (lua_Unsigned)n, h.islittle, size, (n < 0));
   1354         break;
   1355       }
   1356       case Kuint: {  /* unsigned integers */
   1357         lua_Integer n = luaL_checkinteger(L, arg);
   1358         if (size < SZINT)  /* need overflow check? */
   1359           luaL_argcheck(L, (lua_Unsigned)n < ((lua_Unsigned)1 << (size * NB)),
   1360                            arg, "unsigned overflow");
   1361         packint(&b, (lua_Unsigned)n, h.islittle, size, 0);
   1362         break;
   1363       }
   1364       case Kfloat: {  /* floating-point options */
   1365         volatile Ftypes u;
   1366         char *buff = luaL_prepbuffsize(&b, size);
   1367         lua_Number n = luaL_checknumber(L, arg);  /* get argument */
   1368         if (size == sizeof(u.f)) u.f = (float)n;  /* copy it into 'u' */
   1369         else if (size == sizeof(u.d)) u.d = (double)n;
   1370         else u.n = n;
   1371         /* move 'u' to final result, correcting endianness if needed */
   1372         copywithendian(buff, u.buff, size, h.islittle);
   1373         luaL_addsize(&b, size);
   1374         break;
   1375       }
   1376       case Kchar: {  /* fixed-size string */
   1377         size_t len;
   1378         const char *s = luaL_checklstring(L, arg, &len);
   1379         luaL_argcheck(L, len <= (size_t)size, arg,
   1380                          "string longer than given size");
   1381         luaL_addlstring(&b, s, len);  /* add string */
   1382         while (len++ < (size_t)size)  /* pad extra space */
   1383           luaL_addchar(&b, LUAL_PACKPADBYTE);
   1384         break;
   1385       }
   1386       case Kstring: {  /* strings with length count */
   1387         size_t len;
   1388         const char *s = luaL_checklstring(L, arg, &len);
   1389         luaL_argcheck(L, size >= (int)sizeof(size_t) ||
   1390                          len < ((size_t)1 << (size * NB)),
   1391                          arg, "string length does not fit in given size");
   1392         packint(&b, (lua_Unsigned)len, h.islittle, size, 0);  /* pack length */
   1393         luaL_addlstring(&b, s, len);
   1394         totalsize += len;
   1395         break;
   1396       }
   1397       case Kzstr: {  /* zero-terminated string */
   1398         size_t len;
   1399         const char *s = luaL_checklstring(L, arg, &len);
   1400         luaL_argcheck(L, strlen(s) == len, arg, "string contains zeros");
   1401         luaL_addlstring(&b, s, len);
   1402         luaL_addchar(&b, '\0');  /* add zero at the end */
   1403         totalsize += len + 1;
   1404         break;
   1405       }
   1406       case Kpadding: luaL_addchar(&b, LUAL_PACKPADBYTE);  /* FALLTHROUGH */
   1407       case Kpaddalign: case Knop:
   1408         arg--;  /* undo increment */
   1409         break;
   1410     }
   1411   }
   1412   luaL_pushresult(&b);
   1413   return 1;
   1414 }
   1415 
   1416 
   1417 static int str_packsize (lua_State *L) {
   1418   Header h;
   1419   const char *fmt = luaL_checkstring(L, 1);  /* format string */
   1420   size_t totalsize = 0;  /* accumulate total size of result */
   1421   initheader(L, &h);
   1422   while (*fmt != '\0') {
   1423     int size, ntoalign;
   1424     KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign);
   1425     size += ntoalign;  /* total space used by option */
   1426     luaL_argcheck(L, totalsize <= MAXSIZE - size, 1,
   1427                      "format result too large");
   1428     totalsize += size;
   1429     switch (opt) {
   1430       case Kstring:  /* strings with length count */
   1431       case Kzstr:    /* zero-terminated string */
   1432         luaL_argerror(L, 1, "variable-length format");
   1433         /* call never return, but to avoid warnings: *//* FALLTHROUGH */
   1434       default:  break;
   1435     }
   1436   }
   1437   lua_pushinteger(L, (lua_Integer)totalsize);
   1438   return 1;
   1439 }
   1440 
   1441 
   1442 /*
   1443 ** Unpack an integer with 'size' bytes and 'islittle' endianness.
   1444 ** If size is smaller than the size of a Lua integer and integer
   1445 ** is signed, must do sign extension (propagating the sign to the
   1446 ** higher bits); if size is larger than the size of a Lua integer,
   1447 ** it must check the unread bytes to see whether they do not cause an
   1448 ** overflow.
   1449 */
   1450 static lua_Integer unpackint (lua_State *L, const char *str,
   1451                               int islittle, int size, int issigned) {
   1452   lua_Unsigned res = 0;
   1453   int i;
   1454   int limit = (size  <= SZINT) ? size : SZINT;
   1455   for (i = limit - 1; i >= 0; i--) {
   1456     res <<= NB;
   1457     res |= (lua_Unsigned)(unsigned char)str[islittle ? i : size - 1 - i];
   1458   }
   1459   if (size < SZINT) {  /* real size smaller than lua_Integer? */
   1460     if (issigned) {  /* needs sign extension? */
   1461       lua_Unsigned mask = (lua_Unsigned)1 << (size*NB - 1);
   1462       res = ((res ^ mask) - mask);  /* do sign extension */
   1463     }
   1464   }
   1465   else if (size > SZINT) {  /* must check unread bytes */
   1466     int mask = (!issigned || (lua_Integer)res >= 0) ? 0 : MC;
   1467     for (i = limit; i < size; i++) {
   1468       if ((unsigned char)str[islittle ? i : size - 1 - i] != mask)
   1469         luaL_error(L, "%d-byte integer does not fit into Lua Integer", size);
   1470     }
   1471   }
   1472   return (lua_Integer)res;
   1473 }
   1474 
   1475 
   1476 static int str_unpack (lua_State *L) {
   1477   Header h;
   1478   const char *fmt = luaL_checkstring(L, 1);
   1479   size_t ld;
   1480   const char *data = luaL_checklstring(L, 2, &ld);
   1481   size_t pos = (size_t)posrelat(luaL_optinteger(L, 3, 1), ld) - 1;
   1482   int n = 0;  /* number of results */
   1483   luaL_argcheck(L, pos <= ld, 3, "initial position out of string");
   1484   initheader(L, &h);
   1485   while (*fmt != '\0') {
   1486     int size, ntoalign;
   1487     KOption opt = getdetails(&h, pos, &fmt, &size, &ntoalign);
   1488     if ((size_t)ntoalign + size > ~pos || pos + ntoalign + size > ld)
   1489       luaL_argerror(L, 2, "data string too short");
   1490     pos += ntoalign;  /* skip alignment */
   1491     /* stack space for item + next position */
   1492     luaL_checkstack(L, 2, "too many results");
   1493     n++;
   1494     switch (opt) {
   1495       case Kint:
   1496       case Kuint: {
   1497         lua_Integer res = unpackint(L, data + pos, h.islittle, size,
   1498                                        (opt == Kint));
   1499         lua_pushinteger(L, res);
   1500         break;
   1501       }
   1502       case Kfloat: {
   1503         volatile Ftypes u;
   1504         lua_Number num;
   1505         copywithendian(u.buff, data + pos, size, h.islittle);
   1506         if (size == sizeof(u.f)) num = (lua_Number)u.f;
   1507         else if (size == sizeof(u.d)) num = (lua_Number)u.d;
   1508         else num = u.n;
   1509         lua_pushnumber(L, num);
   1510         break;
   1511       }
   1512       case Kchar: {
   1513         lua_pushlstring(L, data + pos, size);
   1514         break;
   1515       }
   1516       case Kstring: {
   1517         size_t len = (size_t)unpackint(L, data + pos, h.islittle, size, 0);
   1518         luaL_argcheck(L, pos + len + size <= ld, 2, "data string too short");
   1519         lua_pushlstring(L, data + pos + size, len);
   1520         pos += len;  /* skip string */
   1521         break;
   1522       }
   1523       case Kzstr: {
   1524         size_t len = (int)strlen(data + pos);
   1525         lua_pushlstring(L, data + pos, len);
   1526         pos += len + 1;  /* skip string plus final '\0' */
   1527         break;
   1528       }
   1529       case Kpaddalign: case Kpadding: case Knop:
   1530         n--;  /* undo increment */
   1531         break;
   1532     }
   1533     pos += size;
   1534   }
   1535   lua_pushinteger(L, pos + 1);  /* next position */
   1536   return n + 1;
   1537 }
   1538 
   1539 /* }====================================================== */
   1540 
   1541 
   1542 static const luaL_Reg strlib[] = {
   1543   {"byte", str_byte},
   1544   {"char", str_char},
   1545   {"dump", str_dump},
   1546   {"find", str_find},
   1547   {"format", str_format},
   1548   {"gmatch", gmatch},
   1549   {"gsub", str_gsub},
   1550   {"len", str_len},
   1551   {"lower", str_lower},
   1552   {"match", str_match},
   1553   {"rep", str_rep},
   1554   {"reverse", str_reverse},
   1555   {"sub", str_sub},
   1556   {"upper", str_upper},
   1557   {"pack", str_pack},
   1558   {"packsize", str_packsize},
   1559   {"unpack", str_unpack},
   1560   {NULL, NULL}
   1561 };
   1562 
   1563 
   1564 static void createmetatable (lua_State *L) {
   1565   lua_createtable(L, 0, 1);  /* table to be metatable for strings */
   1566   lua_pushliteral(L, "");  /* dummy string */
   1567   lua_pushvalue(L, -2);  /* copy table */
   1568   lua_setmetatable(L, -2);  /* set table as metatable for strings */
   1569   lua_pop(L, 1);  /* pop dummy string */
   1570   lua_pushvalue(L, -2);  /* get string library */
   1571   lua_setfield(L, -2, "__index");  /* metatable.__index = string */
   1572   lua_pop(L, 1);  /* pop metatable */
   1573 }
   1574 
   1575 
   1576 /*
   1577 ** Open string library
   1578 */
   1579 LUAMOD_API int luaopen_string (lua_State *L) {
   1580   luaL_newlib(L, strlib);
   1581   createmetatable(L);
   1582   return 1;
   1583 }
   1584