aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lprefix.h9
-rw-r--r--lstrlib.c157
-rw-r--r--ltablib.c41
-rw-r--r--lutf8lib.c4
4 files changed, 126 insertions, 85 deletions
diff --git a/lprefix.h b/lprefix.h
index cd189a5..0eb149f 100644
--- a/lprefix.h
+++ b/lprefix.h
@@ -98,6 +98,15 @@ static const char *compat53_utf8_escape (lua_State* L, long x) {
98# define LUA_INTEGER_FRMLEN "" 98# define LUA_INTEGER_FRMLEN ""
99# define LUA_NUMBER_FRMLEN "" 99# define LUA_NUMBER_FRMLEN ""
100# endif 100# endif
101# ifndef LUA_MININTEGER
102# define LUA_MININTEGER 0
103# endif
104# ifndef LUA_INTEGER_FMT
105# define LUA_INTEGER_FMT "%d"
106# endif
107# ifndef LUAI_UACINT
108# define LUAI_UACINT lua_Integer
109# endif
101/* different Lua 5.3 versions have conflicting variants of this macro 110/* different Lua 5.3 versions have conflicting variants of this macro
102 * in luaconf.h, there's a fallback implementation in lstrlib.c, and 111 * in luaconf.h, there's a fallback implementation in lstrlib.c, and
103 * the macro isn't used for string (un)packing anyway! 112 * the macro isn't used for string (un)packing anyway!
diff --git a/lstrlib.c b/lstrlib.c
index fe30e34..c7aa755 100644
--- a/lstrlib.c
+++ b/lstrlib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lstrlib.c,v 1.239 2015/11/25 16:28:17 roberto Exp $ 2** $Id: lstrlib.c,v 1.254 2016/12/22 13:08:50 roberto Exp $
3** Standard library for string operations and pattern-matching 3** Standard library for string operations and pattern-matching
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -13,6 +13,7 @@
13#include <ctype.h> 13#include <ctype.h>
14#include <float.h> 14#include <float.h>
15#include <limits.h> 15#include <limits.h>
16#include <locale.h>
16#include <stddef.h> 17#include <stddef.h>
17#include <stdio.h> 18#include <stdio.h>
18#include <stdlib.h> 19#include <stdlib.h>
@@ -26,7 +27,8 @@
26 27
27/* 28/*
28** maximum number of captures that a pattern can do during 29** maximum number of captures that a pattern can do during
29** pattern-matching. This limit is arbitrary. 30** pattern-matching. This limit is arbitrary, but must fit in
31** an unsigned char.
30*/ 32*/
31#if !defined(LUA_MAXCAPTURES) 33#if !defined(LUA_MAXCAPTURES)
32#define LUA_MAXCAPTURES 32 34#define LUA_MAXCAPTURES 32
@@ -214,9 +216,8 @@ typedef struct MatchState {
214 const char *src_end; /* end ('\0') of source string */ 216 const char *src_end; /* end ('\0') of source string */
215 const char *p_end; /* end ('\0') of pattern */ 217 const char *p_end; /* end ('\0') of pattern */
216 lua_State *L; 218 lua_State *L;
217 size_t nrep; /* limit to avoid non-linear complexity */
218 int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ 219 int matchdepth; /* control for recursive depth (to avoid C stack overflow) */
219 int level; /* total number of captures (finished or unfinished) */ 220 unsigned char level; /* total number of captures (finished or unfinished) */
220 struct { 221 struct {
221 const char *init; 222 const char *init;
222 ptrdiff_t len; 223 ptrdiff_t len;
@@ -234,17 +235,6 @@ static const char *match (MatchState *ms, const char *s, const char *p);
234#endif 235#endif
235 236
236 237
237/*
238** parameters to control the maximum number of operators handled in
239** a match (to avoid non-linear complexity). The maximum will be:
240** (subject length) * A_REPS + B_REPS
241*/
242#if !defined(A_REPS)
243#define A_REPS 4
244#define B_REPS 100000
245#endif
246
247
248#define L_ESC '%' 238#define L_ESC '%'
249#define SPECIALS "^$*+?.([%-" 239#define SPECIALS "^$*+?.([%-"
250 240
@@ -502,8 +492,6 @@ static const char *match (MatchState *ms, const char *s, const char *p) {
502 s = NULL; /* fail */ 492 s = NULL; /* fail */
503 } 493 }
504 else { /* matched once */ 494 else { /* matched once */
505 if (ms->nrep-- == 0)
506 luaL_error(ms->L, "pattern too complex");
507 switch (*ep) { /* handle optional suffix */ 495 switch (*ep) { /* handle optional suffix */
508 case '?': { /* optional */ 496 case '?': { /* optional */
509 const char *res; 497 const char *res;
@@ -607,10 +595,6 @@ static void prepstate (MatchState *ms, lua_State *L,
607 ms->src_init = s; 595 ms->src_init = s;
608 ms->src_end = s + ls; 596 ms->src_end = s + ls;
609 ms->p_end = p + lp; 597 ms->p_end = p + lp;
610 if (ls < (MAX_SIZET - B_REPS) / A_REPS)
611 ms->nrep = A_REPS * ls + B_REPS;
612 else /* overflow (very long subject) */
613 ms->nrep = MAX_SIZET; /* no limit */
614} 598}
615 599
616 600
@@ -681,6 +665,7 @@ static int str_match (lua_State *L) {
681typedef struct GMatchState { 665typedef struct GMatchState {
682 const char *src; /* current position */ 666 const char *src; /* current position */
683 const char *p; /* pattern */ 667 const char *p; /* pattern */
668 const char *lastmatch; /* end of last match */
684 MatchState ms; /* match state */ 669 MatchState ms; /* match state */
685} GMatchState; 670} GMatchState;
686 671
@@ -688,14 +673,12 @@ typedef struct GMatchState {
688static int gmatch_aux (lua_State *L) { 673static int gmatch_aux (lua_State *L) {
689 GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3)); 674 GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3));
690 const char *src; 675 const char *src;
676 gm->ms.L = L;
691 for (src = gm->src; src <= gm->ms.src_end; src++) { 677 for (src = gm->src; src <= gm->ms.src_end; src++) {
692 const char *e; 678 const char *e;
693 reprepstate(&gm->ms); 679 reprepstate(&gm->ms);
694 if ((e = match(&gm->ms, src, gm->p)) != NULL) { 680 if ((e = match(&gm->ms, src, gm->p)) != NULL && e != gm->lastmatch) {
695 if (e == src) /* empty match? */ 681 gm->src = gm->lastmatch = e;
696 gm->src =src + 1; /* go at least one position */
697 else
698 gm->src = e;
699 return push_captures(&gm->ms, src, e); 682 return push_captures(&gm->ms, src, e);
700 } 683 }
701 } 684 }
@@ -711,7 +694,7 @@ static int gmatch (lua_State *L) {
711 lua_settop(L, 2); /* keep them on closure to avoid being collected */ 694 lua_settop(L, 2); /* keep them on closure to avoid being collected */
712 gm = (GMatchState *)lua_newuserdata(L, sizeof(GMatchState)); 695 gm = (GMatchState *)lua_newuserdata(L, sizeof(GMatchState));
713 prepstate(&gm->ms, L, s, ls, p, lp); 696 prepstate(&gm->ms, L, s, ls, p, lp);
714 gm->src = s; gm->p = p; 697 gm->src = s; gm->p = p; gm->lastmatch = NULL;
715 lua_pushcclosure(L, gmatch_aux, 3); 698 lua_pushcclosure(L, gmatch_aux, 3);
716 return 1; 699 return 1;
717} 700}
@@ -778,12 +761,13 @@ static void add_value (MatchState *ms, luaL_Buffer *b, const char *s,
778 761
779static int str_gsub (lua_State *L) { 762static int str_gsub (lua_State *L) {
780 size_t srcl, lp; 763 size_t srcl, lp;
781 const char *src = luaL_checklstring(L, 1, &srcl); 764 const char *src = luaL_checklstring(L, 1, &srcl); /* subject */
782 const char *p = luaL_checklstring(L, 2, &lp); 765 const char *p = luaL_checklstring(L, 2, &lp); /* pattern */
783 int tr = lua_type(L, 3); 766 const char *lastmatch = NULL; /* end of last match */
784 lua_Integer max_s = luaL_optinteger(L, 4, srcl + 1); 767 int tr = lua_type(L, 3); /* replacement type */
768 lua_Integer max_s = luaL_optinteger(L, 4, srcl + 1); /* max replacements */
785 int anchor = (*p == '^'); 769 int anchor = (*p == '^');
786 lua_Integer n = 0; 770 lua_Integer n = 0; /* replacement count */
787 MatchState ms; 771 MatchState ms;
788 luaL_Buffer b; 772 luaL_Buffer b;
789 luaL_argcheck(L, tr == LUA_TNUMBER || tr == LUA_TSTRING || 773 luaL_argcheck(L, tr == LUA_TNUMBER || tr == LUA_TSTRING ||
@@ -796,16 +780,15 @@ static int str_gsub (lua_State *L) {
796 prepstate(&ms, L, src, srcl, p, lp); 780 prepstate(&ms, L, src, srcl, p, lp);
797 while (n < max_s) { 781 while (n < max_s) {
798 const char *e; 782 const char *e;
799 reprepstate(&ms); 783 reprepstate(&ms); /* (re)prepare state for new match */
800 if ((e = match(&ms, src, p)) != NULL) { 784 if ((e = match(&ms, src, p)) != NULL && e != lastmatch) { /* match? */
801 n++; 785 n++;
802 add_value(&ms, &b, src, e, tr); 786 add_value(&ms, &b, src, e, tr); /* add replacement to buffer */
787 src = lastmatch = e;
803 } 788 }
804 if (e && e>src) /* non empty match? */ 789 else if (src < ms.src_end) /* otherwise, skip one character */
805 src = e; /* skip it */
806 else if (src < ms.src_end)
807 luaL_addchar(&b, *src++); 790 luaL_addchar(&b, *src++);
808 else break; 791 else break; /* end of subject */
809 if (anchor) break; 792 if (anchor) break;
810 } 793 }
811 luaL_addlstring(&b, src, ms.src_end-src); 794 luaL_addlstring(&b, src, ms.src_end-src);
@@ -830,7 +813,6 @@ static int str_gsub (lua_State *L) {
830** Hexadecimal floating-point formatter 813** Hexadecimal floating-point formatter
831*/ 814*/
832 815
833#include <locale.h>
834#include <math.h> 816#include <math.h>
835 817
836#define SIZELENMOD (sizeof(LUA_NUMBER_FRMLEN)/sizeof(char)) 818#define SIZELENMOD (sizeof(LUA_NUMBER_FRMLEN)/sizeof(char))
@@ -857,11 +839,12 @@ static lua_Number adddigit (char *buff, int n, lua_Number x) {
857 839
858 840
859static int num2straux (char *buff, int sz, lua_Number x) { 841static int num2straux (char *buff, int sz, lua_Number x) {
860 if (x != x || x == HUGE_VAL || x == -HUGE_VAL) /* inf or NaN? */ 842 /* if 'inf' or 'NaN', format it like '%g' */
861 return l_sprintf(buff, sz, LUA_NUMBER_FMT, x); /* equal to '%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);
862 else if (x == 0) { /* can be -0... */ 845 else if (x == 0) { /* can be -0... */
863 /* create "0" or "-0" followed by exponent */ 846 /* create "0" or "-0" followed by exponent */
864 return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", x); 847 return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", (LUAI_UACNUMBER)x);
865 } 848 }
866 else { 849 else {
867 int e; 850 int e;
@@ -922,16 +905,14 @@ static int lua_number2strx (lua_State *L, char *buff, int sz,
922#define MAX_FORMAT 32 905#define MAX_FORMAT 32
923 906
924 907
925static void addquoted (lua_State *L, luaL_Buffer *b, int arg) { 908static void addquoted (luaL_Buffer *b, const char *s, size_t len) {
926 size_t l;
927 const char *s = luaL_checklstring(L, arg, &l);
928 luaL_addchar(b, '"'); 909 luaL_addchar(b, '"');
929 while (l--) { 910 while (len--) {
930 if (*s == '"' || *s == '\\' || *s == '\n') { 911 if (*s == '"' || *s == '\\' || *s == '\n') {
931 luaL_addchar(b, '\\'); 912 luaL_addchar(b, '\\');
932 luaL_addchar(b, *s); 913 luaL_addchar(b, *s);
933 } 914 }
934 else if (*s == '\0' || iscntrl(uchar(*s))) { 915 else if (iscntrl(uchar(*s))) {
935 char buff[10]; 916 char buff[10];
936 if (!isdigit(uchar(*(s+1)))) 917 if (!isdigit(uchar(*(s+1))))
937 l_sprintf(buff, sizeof(buff), "\\%d", (int)uchar(*s)); 918 l_sprintf(buff, sizeof(buff), "\\%d", (int)uchar(*s));
@@ -946,6 +927,57 @@ static void addquoted (lua_State *L, luaL_Buffer *b, int arg) {
946 luaL_addchar(b, '"'); 927 luaL_addchar(b, '"');
947} 928}
948 929
930
931/*
932** Ensures the 'buff' string uses a dot as the radix character.
933*/
934static 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
943static 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
949static const char *scanformat (lua_State *L, const char *strfrmt, char *form) { 981static const char *scanformat (lua_State *L, const char *strfrmt, char *form) {
950 const char *p = strfrmt; 982 const char *p = strfrmt;
951 while (*p != '\0' && strchr(FLAGS, *p) != NULL) p++; /* skip flags */ 983 while (*p != '\0' && strchr(FLAGS, *p) != NULL) p++; /* skip flags */
@@ -1010,7 +1042,7 @@ static int str_format (lua_State *L) {
1010 case 'o': case 'u': case 'x': case 'X': { 1042 case 'o': case 'u': case 'x': case 'X': {
1011 lua_Integer n = luaL_checkinteger(L, arg); 1043 lua_Integer n = luaL_checkinteger(L, arg);
1012 addlenmod(form, LUA_INTEGER_FRMLEN); 1044 addlenmod(form, LUA_INTEGER_FRMLEN);
1013 nb = l_sprintf(buff, MAX_ITEM, form, n); 1045 nb = l_sprintf(buff, MAX_ITEM, form, (LUAI_UACINT)n);
1014 break; 1046 break;
1015 } 1047 }
1016 case 'a': case 'A': 1048 case 'a': case 'A':
@@ -1020,12 +1052,13 @@ static int str_format (lua_State *L) {
1020 break; 1052 break;
1021 case 'e': case 'E': case 'f': 1053 case 'e': case 'E': case 'f':
1022 case 'g': case 'G': { 1054 case 'g': case 'G': {
1055 lua_Number n = luaL_checknumber(L, arg);
1023 addlenmod(form, LUA_NUMBER_FRMLEN); 1056 addlenmod(form, LUA_NUMBER_FRMLEN);
1024 nb = l_sprintf(buff, MAX_ITEM, form, luaL_checknumber(L, arg)); 1057 nb = l_sprintf(buff, MAX_ITEM, form, (LUAI_UACNUMBER)n);
1025 break; 1058 break;
1026 } 1059 }
1027 case 'q': { 1060 case 'q': {
1028 addquoted(L, &b, arg); 1061 addliteral(L, &b, arg);
1029 break; 1062 break;
1030 } 1063 }
1031 case 's': { 1064 case 's': {
@@ -1070,8 +1103,8 @@ static int str_format (lua_State *L) {
1070 1103
1071 1104
1072/* value used for padding */ 1105/* value used for padding */
1073#if !defined(LUA_PACKPADBYTE) 1106#if !defined(LUAL_PACKPADBYTE)
1074#define LUA_PACKPADBYTE 0x00 1107#define LUAL_PACKPADBYTE 0x00
1075#endif 1108#endif
1076 1109
1077/* maximum size for the binary representation of an integer */ 1110/* maximum size for the binary representation of an integer */
@@ -1228,7 +1261,7 @@ static KOption getoption (Header *h, const char **fmt, int *size) {
1228** 'psize' is filled with option's size, 'notoalign' with its 1261** 'psize' is filled with option's size, 'notoalign' with its
1229** alignment requirements. 1262** alignment requirements.
1230** Local variable 'size' gets the size to be aligned. (Kpadal option 1263** Local variable 'size' gets the size to be aligned. (Kpadal option
1231** always gets its full alignment, other options are limited by 1264** always gets its full alignment, other options are limited by
1232** the maximum alignment ('maxalign'). Kchar option needs no alignment 1265** the maximum alignment ('maxalign'). Kchar option needs no alignment
1233** despite its size. 1266** despite its size.
1234*/ 1267*/
@@ -1308,7 +1341,7 @@ static int str_pack (lua_State *L) {
1308 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign); 1341 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign);
1309 totalsize += ntoalign + size; 1342 totalsize += ntoalign + size;
1310 while (ntoalign-- > 0) 1343 while (ntoalign-- > 0)
1311 luaL_addchar(&b, LUA_PACKPADBYTE); /* fill alignment */ 1344 luaL_addchar(&b, LUAL_PACKPADBYTE); /* fill alignment */
1312 arg++; 1345 arg++;
1313 switch (opt) { 1346 switch (opt) {
1314 case Kint: { /* signed integers */ 1347 case Kint: { /* signed integers */
@@ -1343,13 +1376,11 @@ static int str_pack (lua_State *L) {
1343 case Kchar: { /* fixed-size string */ 1376 case Kchar: { /* fixed-size string */
1344 size_t len; 1377 size_t len;
1345 const char *s = luaL_checklstring(L, arg, &len); 1378 const char *s = luaL_checklstring(L, arg, &len);
1346 if ((size_t)size <= len) /* string larger than (or equal to) needed? */ 1379 luaL_argcheck(L, len <= (size_t)size, arg,
1347 luaL_addlstring(&b, s, size); /* truncate string to asked size */ 1380 "string longer than given size");
1348 else { /* string smaller than needed */ 1381 luaL_addlstring(&b, s, len); /* add string */
1349 luaL_addlstring(&b, s, len); /* add it all */ 1382 while (len++ < (size_t)size) /* pad extra space */
1350 while (len++ < (size_t)size) /* pad extra space */ 1383 luaL_addchar(&b, LUAL_PACKPADBYTE);
1351 luaL_addchar(&b, LUA_PACKPADBYTE);
1352 }
1353 break; 1384 break;
1354 } 1385 }
1355 case Kstring: { /* strings with length count */ 1386 case Kstring: { /* strings with length count */
@@ -1372,7 +1403,7 @@ static int str_pack (lua_State *L) {
1372 totalsize += len + 1; 1403 totalsize += len + 1;
1373 break; 1404 break;
1374 } 1405 }
1375 case Kpadding: luaL_addchar(&b, LUA_PACKPADBYTE); /* FALLTHROUGH */ 1406 case Kpadding: luaL_addchar(&b, LUAL_PACKPADBYTE); /* FALLTHROUGH */
1376 case Kpaddalign: case Knop: 1407 case Kpaddalign: case Knop:
1377 arg--; /* undo increment */ 1408 arg--; /* undo increment */
1378 break; 1409 break;
diff --git a/ltablib.c b/ltablib.c
index b3c9a7c..98b2f87 100644
--- a/ltablib.c
+++ b/ltablib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltablib.c,v 1.90 2015/11/25 12:48:57 roberto Exp $ 2** $Id: ltablib.c,v 1.93 2016/02/25 19:41:54 roberto Exp $
3** Library for Table Manipulation 3** Library for Table Manipulation
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -53,7 +53,7 @@ static void checktab (lua_State *L, int arg, int what) {
53 lua_pop(L, n); /* pop metatable and tested metamethods */ 53 lua_pop(L, n); /* pop metatable and tested metamethods */
54 } 54 }
55 else 55 else
56 luaL_argerror(L, arg, "table expected"); /* force an error */ 56 luaL_checktype(L, arg, LUA_TTABLE); /* force an error */
57 } 57 }
58} 58}
59 59
@@ -139,7 +139,7 @@ static int tmove (lua_State *L) {
139 n = e - f + 1; /* number of elements to move */ 139 n = e - f + 1; /* number of elements to move */
140 luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, 140 luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4,
141 "destination wrap around"); 141 "destination wrap around");
142 if (t > e || t <= f || tt != 1) { 142 if (t > e || t <= f || (tt != 1 && !lua_compare(L, 1, tt, LUA_OPEQ))) {
143 for (i = 0; i < n; i++) { 143 for (i = 0; i < n; i++) {
144 lua_geti(L, 1, f + i); 144 lua_geti(L, 1, f + i);
145 lua_seti(L, tt, t + i); 145 lua_seti(L, tt, t + i);
@@ -152,7 +152,7 @@ static int tmove (lua_State *L) {
152 } 152 }
153 } 153 }
154 } 154 }
155 lua_pushvalue(L, tt); /* return "to table" */ 155 lua_pushvalue(L, tt); /* return destination table */
156 return 1; 156 return 1;
157} 157}
158 158
@@ -172,7 +172,7 @@ static int tconcat (lua_State *L) {
172 size_t lsep; 172 size_t lsep;
173 const char *sep = luaL_optlstring(L, 2, "", &lsep); 173 const char *sep = luaL_optlstring(L, 2, "", &lsep);
174 lua_Integer i = luaL_optinteger(L, 3, 1); 174 lua_Integer i = luaL_optinteger(L, 3, 1);
175 last = luaL_opt(L, luaL_checkinteger, 4, last); 175 last = luaL_optinteger(L, 4, last);
176 luaL_buffinit(L, &b); 176 luaL_buffinit(L, &b);
177 for (; i < last; i++) { 177 for (; i < last; i++) {
178 addfield(L, &b, i); 178 addfield(L, &b, i);
@@ -232,6 +232,10 @@ static int unpack (lua_State *L) {
232*/ 232*/
233 233
234 234
235/* type for array indices */
236typedef unsigned int IdxT;
237
238
235/* 239/*
236** Produce a "random" 'unsigned int' to randomize pivot choice. This 240** Produce a "random" 'unsigned int' to randomize pivot choice. This
237** macro is used only when 'sort' detects a big imbalance in the result 241** macro is used only when 'sort' detects a big imbalance in the result
@@ -270,7 +274,7 @@ static unsigned int l_randomizePivot (void) {
270#define RANLIMIT 100u 274#define RANLIMIT 100u
271 275
272 276
273static void set2 (lua_State *L, unsigned int i, unsigned int j) { 277static void set2 (lua_State *L, IdxT i, IdxT j) {
274 lua_seti(L, 1, i); 278 lua_seti(L, 1, i);
275 lua_seti(L, 1, j); 279 lua_seti(L, 1, j);
276} 280}
@@ -303,10 +307,9 @@ static int sort_comp (lua_State *L, int a, int b) {
303** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] 307** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
304** returns 'i'. 308** returns 'i'.
305*/ 309*/
306static unsigned int partition (lua_State *L, unsigned int lo, 310static IdxT partition (lua_State *L, IdxT lo, IdxT up) {
307 unsigned int up) { 311 IdxT i = lo; /* will be incremented before first use */
308 unsigned int i = lo; /* will be incremented before first use */ 312 IdxT j = up - 1; /* will be decremented before first use */
309 unsigned int j = up - 1; /* will be decremented before first use */
310 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ 313 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */
311 for (;;) { 314 for (;;) {
312 /* next loop: repeat ++i while a[i] < P */ 315 /* next loop: repeat ++i while a[i] < P */
@@ -340,10 +343,9 @@ static unsigned int partition (lua_State *L, unsigned int lo,
340** Choose an element in the middle (2nd-3th quarters) of [lo,up] 343** Choose an element in the middle (2nd-3th quarters) of [lo,up]
341** "randomized" by 'rnd' 344** "randomized" by 'rnd'
342*/ 345*/
343static unsigned int choosePivot (unsigned int lo, unsigned int up, 346static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) {
344 unsigned int rnd) { 347 IdxT r4 = (up - lo) / 4; /* range/4 */
345 unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ 348 IdxT p = rnd % (r4 * 2) + (lo + r4);
346 unsigned int p = rnd % (r4 * 2) + (lo + r4);
347 lua_assert(lo + r4 <= p && p <= up - r4); 349 lua_assert(lo + r4 <= p && p <= up - r4);
348 return p; 350 return p;
349} 351}
@@ -352,11 +354,11 @@ static unsigned int choosePivot (unsigned int lo, unsigned int up,
352/* 354/*
353** QuickSort algorithm (recursive function) 355** QuickSort algorithm (recursive function)
354*/ 356*/
355static void auxsort (lua_State *L, unsigned int lo, unsigned int up, 357static void auxsort (lua_State *L, IdxT lo, IdxT up,
356 unsigned int rnd) { 358 unsigned int rnd) {
357 while (lo < up) { /* loop for tail recursion */ 359 while (lo < up) { /* loop for tail recursion */
358 unsigned int p; /* Pivot index */ 360 IdxT p; /* Pivot index */
359 unsigned int n; /* to be used later */ 361 IdxT n; /* to be used later */
360 /* sort elements 'lo', 'p', and 'up' */ 362 /* sort elements 'lo', 'p', and 'up' */
361 lua_geti(L, 1, lo); 363 lua_geti(L, 1, lo);
362 lua_geti(L, 1, up); 364 lua_geti(L, 1, up);
@@ -400,7 +402,7 @@ static void auxsort (lua_State *L, unsigned int lo, unsigned int up,
400 n = up - p; /* size of smaller interval */ 402 n = up - p; /* size of smaller interval */
401 up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ 403 up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */
402 } 404 }
403 if ((up - lo) / 128u > n) /* partition too imbalanced? */ 405 if ((up - lo) / 128 > n) /* partition too imbalanced? */
404 rnd = l_randomizePivot(); /* try a new randomization */ 406 rnd = l_randomizePivot(); /* try a new randomization */
405 } /* tail call auxsort(L, lo, up, rnd) */ 407 } /* tail call auxsort(L, lo, up, rnd) */
406} 408}
@@ -410,11 +412,10 @@ static int sort (lua_State *L) {
410 lua_Integer n = aux_getn(L, 1, TAB_RW); 412 lua_Integer n = aux_getn(L, 1, TAB_RW);
411 if (n > 1) { /* non-trivial interval? */ 413 if (n > 1) { /* non-trivial interval? */
412 luaL_argcheck(L, n < INT_MAX, 1, "array too big"); 414 luaL_argcheck(L, n < INT_MAX, 1, "array too big");
413 luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */
414 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ 415 if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */
415 luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ 416 luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */
416 lua_settop(L, 2); /* make sure there are two arguments */ 417 lua_settop(L, 2); /* make sure there are two arguments */
417 auxsort(L, 1, (unsigned int)n, 0u); 418 auxsort(L, 1, (IdxT)n, 0);
418 } 419 }
419 return 0; 420 return 0;
420} 421}
diff --git a/lutf8lib.c b/lutf8lib.c
index 9042582..de9e3dc 100644
--- a/lutf8lib.c
+++ b/lutf8lib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lutf8lib.c,v 1.15 2015/03/28 19:16:55 roberto Exp $ 2** $Id: lutf8lib.c,v 1.16 2016/12/22 13:08:50 roberto Exp $
3** Standard library for UTF-8 manipulation 3** Standard library for UTF-8 manipulation
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -194,7 +194,7 @@ static int byteoffset (lua_State *L) {
194 lua_pushinteger(L, posi + 1); 194 lua_pushinteger(L, posi + 1);
195 else /* no such character */ 195 else /* no such character */
196 lua_pushnil(L); 196 lua_pushnil(L);
197 return 1; 197 return 1;
198} 198}
199 199
200 200