diff options
| -rw-r--r-- | ChangeLog | 14 | ||||
| -rw-r--r-- | bignum.c | 187 | ||||
| -rw-r--r-- | internal.h | 37 | ||||
| -rw-r--r-- | pack.c | 37 | ||||
| -rw-r--r-- | test/-ext-/bignum/test_pack.rb | 76 |
5 files changed, 311 insertions, 40 deletions
@@ -1,3 +1,17 @@ +Sat Jun 22 02:18:07 2013 Tanaka Akira <akr@fsij.org> + + * bignum.c (bary_pack): Specialized packers implemented. + (HOST_BIGENDIAN_P): New macro. + (ALIGNOF): New macro. + (CLEAR_LOWBITS): New macro. + (FILL_LOWBITS): New macro. + (swap_bdigit): New macro. + (bary_2comp): Returns an int. + + * internal.h (swap16): Moved from pack.c + (swap32): Ditto. + (swap64): Ditto. + Fri Jun 21 21:29:49 2013 Masaya Tarui <tarui@ruby-lang.org> * gc.c (typedef enum): Introduce flags of major gc reason. @@ -33,6 +33,15 @@ static VALUE big_three = Qnil; #define USHORT _USHORT #endif +#ifdef WORDS_BIGENDIAN +# define HOST_BIGENDIAN_P 1 +#else +# define HOST_BIGENDIAN_P 0 +#endif +#define ALIGNOF(type) ((int)offsetof(struct { char f1; type f2; }, f2)) +#define CLEAR_LOWBITS(d, numbits) (sizeof(d) * CHAR_BIT <= (numbits) ? 0 : ((d) >> (numbits)) << (numbits)) +#define FILL_LOWBITS(d, numbits) (sizeof(d) * CHAR_BIT <= (numbits) ? ~((d)*0) : (d) | ((((d)*0+1) << (numbits))-1)) + #define BDIGITS(x) (RBIGNUM_DIGITS(x)) #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT) #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG) @@ -48,6 +57,14 @@ static VALUE big_three = Qnil; #define BIGLO(x) ((BDIGIT)((x) & BDIGMAX)) #define BDIGMAX ((BDIGIT)(BIGRAD-1)) +#if SIZEOF_BDIGITS == 2 +# define swap_bdigit(x) swap16(x) +#elif SIZEOF_BDIGITS == 4 +# define swap_bdigit(x) swap32(x) +#elif SIZEOF_BDIGITS == 8 +# define swap_bdigit(x) swap64(x) +#endif + #define BIGZEROP(x) (RBIGNUM_LEN(x) == 0 || \ (BDIGITS(x)[0] == 0 && \ (RBIGNUM_LEN(x) == 1 || bigzero_p(x)))) @@ -76,7 +93,7 @@ static void bary_sub(BDIGIT *zds, size_t zn, BDIGIT *xds, size_t xn, BDIGIT *yds static void bary_divmod(BDIGIT *qds, size_t nq, BDIGIT *rds, size_t nr, BDIGIT *xds, size_t nx, BDIGIT *yds, size_t ny); static void bary_add(BDIGIT *zds, size_t zn, BDIGIT *xds, size_t xn, BDIGIT *yds, size_t yn); static int bary_pack(int sign, BDIGIT *ds, size_t num_bdigits, void *words, size_t numwords, size_t wordsize, size_t nails, int flags); -static BDIGIT bary_2comp(BDIGIT *ds, size_t n); +static int bary_2comp(BDIGIT *ds, size_t n); #define BIGNUM_DEBUG 0 #if BIGNUM_DEBUG @@ -231,7 +248,7 @@ rb_big_clone(VALUE x) return z; } -static BDIGIT +static int bary_2comp(BDIGIT *ds, size_t n) { size_t i = n; @@ -244,7 +261,7 @@ bary_2comp(BDIGIT *ds, size_t n) ds[i++] = BIGLO(num); num = BIGDN(num); } while (i < n); - return (BDIGIT)num; + return num != 0; } /* modify a bignum by 2's complement */ @@ -901,6 +918,170 @@ bary_pack(int sign, BDIGIT *ds, size_t num_bdigits, void *words, size_t numwords sign = 0; } + if (nails == 0 && sign == 0) { + MEMZERO(words, unsigned char, numwords * wordsize); + return 0; + } + if (nails == 0 && numwords == 1) { + int need_swap = wordsize != 1 && + (flags & INTEGER_PACK_BYTEORDER_MASK) != INTEGER_PACK_NATIVE_BYTE_ORDER && + ((flags & INTEGER_PACK_MSBYTE_FIRST) ? !HOST_BIGENDIAN_P : HOST_BIGENDIAN_P); + if (0 < sign || !(flags & INTEGER_PACK_2COMP)) { + BDIGIT d; + if (wordsize == 1) { + *((unsigned char *)words) = (unsigned char)(d = dp[0]); + return ((1 < de - dp || CLEAR_LOWBITS(d, 8) != 0) ? 2 : 1) * sign; + } +#if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGITS + if (wordsize == 2 && (uintptr_t)words % ALIGNOF(uint16_t) == 0) { + uint16_t u = (uint16_t)(d = dp[0]); + if (need_swap) u = swap16(u); + *((uint16_t *)words) = u; + return ((1 < de - dp || CLEAR_LOWBITS(d, 16) != 0) ? 2 : 1) * sign; + } +#endif +#if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGITS + if (wordsize == 4 && (uintptr_t)words % ALIGNOF(uint32_t) == 0) { + uint32_t u = (uint32_t)(d = dp[0]); + if (need_swap) u = swap32(u); + *((uint32_t *)words) = u; + return ((1 < de - dp || CLEAR_LOWBITS(d, 32) != 0) ? 2 : 1) * sign; + } +#endif +#if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGITS + if (wordsize == 8 && (uintptr_t)words % ALIGNOF(uint64_t) == 0) { + uint64_t u = (uint64_t)(d = dp[0]); + if (need_swap) u = swap64(u); + *((uint64_t *)words) = u; + return ((1 < de - dp || CLEAR_LOWBITS(d, 64) != 0) ? 2 : 1) * sign; + } +#endif + } + else { /* sign < 0 && (flags & INTEGER_PACK_2COMP) */ + BDIGIT_DBL_SIGNED d; + if (wordsize == 1) { + *((unsigned char *)words) = (unsigned char)(d = -(BDIGIT_DBL_SIGNED)dp[0]); + return (1 < de - dp || FILL_LOWBITS(d, 8) != -1) ? -2 : -1; + } +#if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGITS + if (wordsize == 2 && (uintptr_t)words % ALIGNOF(uint16_t) == 0) { + uint16_t u = (uint16_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]); + if (need_swap) u = swap16(u); + *((uint16_t *)words) = u; + return (wordsize == SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 : + (1 < de - dp || FILL_LOWBITS(d, 16) != -1) ? -2 : -1; + } +#endif +#if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGITS + if (wordsize == 4 && (uintptr_t)words % ALIGNOF(uint32_t) == 0) { + uint32_t u = (uint32_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]); + if (need_swap) u = swap32(u); + *((uint32_t *)words) = u; + return (wordsize == SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 : + (1 < de - dp || FILL_LOWBITS(d, 32) != -1) ? -2 : -1; + } +#endif +#if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGITS + if (wordsize == 8 && (uintptr_t)words % ALIGNOF(uint64_t) == 0) { + uint64_t u = (uint64_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]); + if (need_swap) u = swap64(u); + *((uint64_t *)words) = u; + return (wordsize == SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 : + (1 < de - dp || FILL_LOWBITS(d, 64) != -1) ? -2 : -1; + } +#endif + } + } +#if !defined(WORDS_BIGENDIAN) + if (nails == 0 && SIZEOF_BDIGITS == sizeof(BDIGIT) && + (flags & INTEGER_PACK_WORDORDER_MASK) == INTEGER_PACK_LSWORD_FIRST && + (flags & INTEGER_PACK_BYTEORDER_MASK) != INTEGER_PACK_MSBYTE_FIRST) { + size_t src_size = num_bdigits * SIZEOF_BDIGITS; + size_t dst_size = numwords * wordsize; + int overflow = 0; + while (0 < src_size && ((unsigned char *)ds)[src_size-1] == 0) + src_size--; + if (src_size <= dst_size) { + MEMCPY(words, dp, char, src_size); + MEMZERO((char*)words + src_size, char, dst_size - src_size); + } + else { + MEMCPY(words, dp, char, dst_size); + overflow = 1; + } + if (sign < 0 && (flags & INTEGER_PACK_2COMP)) { + unsigned char *p = words, *e = (unsigned char *)words + dst_size; + while (p < e && *p == 0) + p++; + if (p < e) { + *p = 1 + (unsigned char)~*p; + p++; + while (p < e) { + *p = (unsigned char)~*p; + p++; + } + } + else if (overflow) { + p = (unsigned char *)dp + dst_size; + e = (unsigned char *)dp + src_size; + if (p < e && *p++ == 1) { + while (p < e && *p == 0) + p++; + if (p == e) + overflow = 0; + } + } + } + if (overflow) + sign *= 2; + return sign; + } +#endif + if (nails == 0 && SIZEOF_BDIGITS == sizeof(BDIGIT) && + wordsize % SIZEOF_BDIGITS == 0 && (uintptr_t)words % ALIGNOF(BDIGIT) == 0) { + size_t buf_num_bdigits = numwords * wordsize / SIZEOF_BDIGITS; + int need_swap = + (flags & INTEGER_PACK_BYTEORDER_MASK) != INTEGER_PACK_NATIVE_BYTE_ORDER && + ((flags & INTEGER_PACK_MSBYTE_FIRST) ? !HOST_BIGENDIAN_P : HOST_BIGENDIAN_P); + size_t i; + int overflow = 0; + if (num_bdigits <= buf_num_bdigits) { + MEMCPY(words, dp, BDIGIT, num_bdigits); + MEMZERO((BDIGIT*)words + num_bdigits, BDIGIT, buf_num_bdigits - num_bdigits); + } + else { + MEMCPY(words, dp, BDIGIT, buf_num_bdigits); + overflow = 1; + } + if (sign < 0 && (flags & INTEGER_PACK_2COMP)) { + int zero_p = bary_2comp(words, buf_num_bdigits); + if (overflow && + buf_num_bdigits == num_bdigits-1 && + dp[buf_num_bdigits] == 1 && + zero_p) + overflow = 0; + } + if (need_swap) { + for (i = 0; i < buf_num_bdigits; i++) { + BDIGIT d = ((BDIGIT*)words)[i]; + ((BDIGIT*)words)[i] = swap_bdigit(d); + } + } + if (flags & INTEGER_PACK_MSWORD_FIRST) { + BDIGIT *p1 = words, *p2 = p1 + buf_num_bdigits - 1; + while (p1 < p2) { + BDIGIT tmp = *p1; + *p1 = *p2; + *p2 = tmp; + p1++; + p2--; + } + } + if (overflow) + sign *= 2; + return sign; + } + buf = words; bufend = buf + numwords * wordsize; diff --git a/internal.h b/internal.h index 267d388363..de4403761e 100644 --- a/internal.h +++ b/internal.h @@ -73,6 +73,43 @@ extern "C" { (INTEGER_PACK_MSWORD_FIRST | \ INTEGER_PACK_MSBYTE_FIRST) +#ifndef swap16 +# define swap16(x) ((uint16_t)((((x)&0xFF)<<8) | (((x)>>8)&0xFF))) +#endif + +#ifndef swap32 +# if GCC_VERSION_SINCE(4,3,0) +# define swap32(x) __builtin_bswap32(x) +# endif +#endif + +#ifndef swap32 +# define swap32(x) ((uint32_t)((((x)&0xFF)<<24) \ + |(((x)>>24)&0xFF) \ + |(((x)&0x0000FF00)<<8) \ + |(((x)&0x00FF0000)>>8) )) +#endif + +#ifndef swap64 +# if GCC_VERSION_SINCE(4,3,0) +# define swap64(x) __builtin_bswap64(x) +# endif +#endif + +#ifndef swap64 +# ifdef HAVE_INT64_T +# define byte_in_64bit(n) ((uint64_t)0xff << (n)) +# define swap64(x) ((uint64_t)((((x)&byte_in_64bit(0))<<56) \ + |(((x)>>56)&0xFF) \ + |(((x)&byte_in_64bit(8))<<40) \ + |(((x)&byte_in_64bit(48))>>40) \ + |(((x)&byte_in_64bit(16))<<24) \ + |(((x)&byte_in_64bit(40))>>24) \ + |(((x)&byte_in_64bit(24))<<8) \ + |(((x)&byte_in_64bit(32))>>8))) +# endif +#endif + struct rb_deprecated_classext_struct { char conflict[sizeof(VALUE) * 3]; }; @@ -100,43 +100,6 @@ TOKEN_PASTE(swap,x)(xtype z) \ return r; \ } -#ifndef swap32 -# if GCC_VERSION_SINCE(4,3,0) -# define swap32(x) __builtin_bswap32(x) -# endif -#endif - -#ifndef swap64 -# if GCC_VERSION_SINCE(4,3,0) -# define swap64(x) __builtin_bswap64(x) -# endif -#endif - -#ifndef swap16 -# define swap16(x) ((uint16_t)((((x)&0xFF)<<8) | (((x)>>8)&0xFF))) -#endif - -#ifndef swap32 -# define swap32(x) ((uint32_t)((((x)&0xFF)<<24) \ - |(((x)>>24)&0xFF) \ - |(((x)&0x0000FF00)<<8) \ - |(((x)&0x00FF0000)>>8) )) -#endif - -#ifndef swap64 -# ifdef HAVE_INT64_T -# define byte_in_64bit(n) ((uint64_t)0xff << (n)) -# define swap64(x) ((uint64_t)((((x)&byte_in_64bit(0))<<56) \ - |(((x)>>56)&0xFF) \ - |(((x)&byte_in_64bit(8))<<40) \ - |(((x)&byte_in_64bit(48))>>40) \ - |(((x)&byte_in_64bit(16))<<24) \ - |(((x)&byte_in_64bit(40))>>24) \ - |(((x)&byte_in_64bit(24))<<8) \ - |(((x)&byte_in_64bit(32))>>8))) -# endif -#endif - #if SIZEOF_SHORT == 2 # define swaps(x) swap16(x) #elif SIZEOF_SHORT == 4 diff --git a/test/-ext-/bignum/test_pack.rb b/test/-ext-/bignum/test_pack.rb index c2c19a32a2..202395324b 100644 --- a/test/-ext-/bignum/test_pack.rb +++ b/test/-ext-/bignum/test_pack.rb @@ -69,6 +69,55 @@ class TestBignum < Test::Unit::TestCase assert_equal([1, "\x00\x12\x00\x34\x00\x56\x00\x78"], 0x12345678.test_pack(4, 2, 8, BIG_ENDIAN)) end + def test_pack_overflow + assert_equal([-2, "\x1"], (-0x11).test_pack(1, 1, 4, BIG_ENDIAN)) + assert_equal([-2, "\x0"], (-0x10).test_pack(1, 1, 4, BIG_ENDIAN)) + assert_equal([-1, "\xF"], (-0x0F).test_pack(1, 1, 4, BIG_ENDIAN)) + assert_equal([+1, "\xF"], (+0x0F).test_pack(1, 1, 4, BIG_ENDIAN)) + assert_equal([+2, "\x0"], (+0x10).test_pack(1, 1, 4, BIG_ENDIAN)) + assert_equal([+2, "\x1"], (+0x11).test_pack(1, 1, 4, BIG_ENDIAN)) + + assert_equal([-2, "\x01"], (-0x101).test_pack(1, 1, 0, BIG_ENDIAN)) + assert_equal([-2, "\x00"], (-0x100).test_pack(1, 1, 0, BIG_ENDIAN)) + assert_equal([-1, "\xFF"], (-0x0FF).test_pack(1, 1, 0, BIG_ENDIAN)) + assert_equal([+1, "\xFF"], (+0x0FF).test_pack(1, 1, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00"], (+0x100).test_pack(1, 1, 0, BIG_ENDIAN)) + assert_equal([+2, "\x01"], (+0x101).test_pack(1, 1, 0, BIG_ENDIAN)) + + assert_equal([-2, "\x00\x00\x00\x00\x00\x00\x00\x01"], (-0x10000000000000001).test_pack(2, 4, 0, BIG_ENDIAN)) + assert_equal([-2, "\x00\x00\x00\x00\x00\x00\x00\x00"], (-0x10000000000000000).test_pack(2, 4, 0, BIG_ENDIAN)) + assert_equal([-1, "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"], (-0x0FFFFFFFFFFFFFFFF).test_pack(2, 4, 0, BIG_ENDIAN)) + assert_equal([+1, "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"], (+0x0FFFFFFFFFFFFFFFF).test_pack(2, 4, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x00"], (+0x10000000000000000).test_pack(2, 4, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x01"], (+0x10000000000000001).test_pack(2, 4, 0, BIG_ENDIAN)) + + 1.upto(16) {|wordsize| + 1.upto(20) {|numwords| + w = numwords*wordsize + n = 256**w + assert_equal([-2, "\x00"*(w-1)+"\x01"], (-n-1).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + assert_equal([-2, "\x00"*w], (-n ).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + assert_equal([-1, "\xFF"*w], (-n+1).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + assert_equal([+1, "\xFF"*w], (+n-1).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00"*w], (+n ).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00"*(w-1)+"\x01"], (+n+1).test_pack(numwords, wordsize, 0, BIG_ENDIAN)) + } + } + + 1.upto(16) {|wordsize| + 1.upto(20) {|numwords| + w = numwords*wordsize + n = 256**w + assert_equal([-2, "\x01"+"\x00"*(w-1)], (-n-1).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + assert_equal([-2, "\x00"*w], (-n ).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + assert_equal([-1, "\xFF"*w], (-n+1).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + assert_equal([+1, "\xFF"*w], (+n-1).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + assert_equal([+2, "\x00"*w], (+n ).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + assert_equal([+2, "\x01"+"\x00"*(w-1)], (+n+1).test_pack(numwords, wordsize, 0, LITTLE_ENDIAN)) + } + } + end + def test_pack_sign assert_equal([-1, "\x01"], (-1).test_pack(1, 1, 0, BIG_ENDIAN)) assert_equal([-1, "\x80\x70\x60\x50\x40\x30\x20\x10"], (-0x8070605040302010).test_pack(8, 1, 0, BIG_ENDIAN)) @@ -116,6 +165,33 @@ class TestBignum < Test::Unit::TestCase assert_equal([+1, "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"], (+0x0FFFFFFFFFFFFFFFF).test_pack(2, 4, 0, TWOCOMP|BIG_ENDIAN)) assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x00"], (+0x10000000000000000).test_pack(2, 4, 0, TWOCOMP|BIG_ENDIAN)) assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x01"], (+0x10000000000000001).test_pack(2, 4, 0, TWOCOMP|BIG_ENDIAN)) + + 1.upto(16) {|wordsize| + 1.upto(20) {|numwords| + w = numwords*wordsize + n = 256**w + assert_equal([-2, "\xFF"*w ], (-n-1).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + assert_equal([-1, "\x00"*w], (-n ).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + assert_equal([-1, "\x00"*(w-1)+"\x01"], (-n+1).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + assert_equal([+1, "\xFF"*w], (+n-1).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + assert_equal([+2, "\x00"*w], (+n ).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + assert_equal([+2, "\x00"*(w-1)+"\x01"], (+n+1).test_pack(numwords, wordsize, 0, TWOCOMP|BIG_ENDIAN)) + } + } + + 1.upto(16) {|wordsize| + 1.upto(20) {|numwords| + w = numwords*wordsize + n = 256**w + assert_equal([-2, "\xFF"*w ], (-n-1).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + assert_equal([-1, "\x00"*w], (-n ).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + assert_equal([-1, "\x01"+"\x00"*(w-1)], (-n+1).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + assert_equal([+1, "\xFF"*w], (+n-1).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + assert_equal([+2, "\x00"*w], (+n ).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + assert_equal([+2, "\x01"+"\x00"*(w-1)], (+n+1).test_pack(numwords, wordsize, 0, TWOCOMP|LITTLE_ENDIAN)) + } + } + end def test_unpack_zero |