aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
diff options
context:
space:
mode:
authorLukas Larsson <[email protected]>2012-09-05 20:43:03 +0200
committerLukas Larsson <[email protected]>2013-02-14 15:36:44 +0100
commitb074099cc6bdb81285a17e0248373f199c695719 (patch)
tree81e4fd6866506fc1a02e8692fc108c65716d61cf /erts/emulator/beam
parente55aff9434072dc9ba45b610d2e5110b0d537692 (diff)
downloadotp-b074099cc6bdb81285a17e0248373f199c695719.tar.gz
otp-b074099cc6bdb81285a17e0248373f199c695719.tar.bz2
otp-b074099cc6bdb81285a17e0248373f199c695719.zip
Add new binary conversion bifs
Added: binary_to_integer/1,2, integer_to_binary/1,2
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/bif.c50
-rw-r--r--erts/emulator/beam/bif.tab4
-rw-r--r--erts/emulator/beam/big.c247
-rw-r--r--erts/emulator/beam/big.h3
-rw-r--r--erts/emulator/beam/binary.c92
5 files changed, 380 insertions, 16 deletions
diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c
index df084e1185..a596068527 100644
--- a/erts/emulator/beam/bif.c
+++ b/erts/emulator/beam/bif.c
@@ -2895,20 +2895,64 @@ BIF_RETTYPE string_to_integer_1(BIF_ALIST_1)
BIF_RET(TUPLE2(hp, res, tail));
}
}
-
BIF_RETTYPE list_to_integer_1(BIF_ALIST_1)
-{
+ {
+ /* Using do_list_to_integer is about twice as fast as using
+ erts_chars_to_integer because we do not have to copy the
+ entire list */
Eterm res;
Eterm dummy;
/* must be a list */
-
if (do_list_to_integer(BIF_P,BIF_ARG_1,&res,&dummy) != LTI_ALL_INTEGER) {
BIF_ERROR(BIF_P,BADARG);
}
BIF_RET(res);
}
+BIF_RETTYPE list_to_integer_2(BIF_ALIST_2)
+{
+
+ /* Bif implementation is about 50% faster than pure erlang,
+ and since we have erts_chars_to_integer now it is simpler
+ as well. This could be optmized further if we did not have to
+ copy the list to buf. */
+ int i;
+ Eterm res;
+ char *buf = NULL;
+ int base;
+
+ i = list_length(BIF_ARG_1);
+ if (i < 0)
+ BIF_ERROR(BIF_P, BADARG);
+
+ base = signed_val(BIF_ARG_2);
+
+ if (base < 2 || base > 36)
+ BIF_ERROR(BIF_P, BADARG);
+
+ /* Take fast path if base it 10 */
+ if (base == 10)
+ return list_to_integer_1(BIF_P,&BIF_ARG_1);
+
+ buf = (char *) erts_alloc(ERTS_ALC_T_TMP, i + 1);
+
+ if (intlist_to_buf(BIF_ARG_1, buf, i) < 0)
+ goto list_to_integer_1_error;
+ buf[i] = '\0'; /* null terminal */
+
+ if ((res = erts_chars_to_integer(BIF_P,buf,i,base)) == THE_NON_VALUE)
+ goto list_to_integer_1_error;
+
+ erts_free(ERTS_ALC_T_TMP, (void *) buf);
+ BIF_RET(res);
+
+ list_to_integer_1_error:
+ erts_free(ERTS_ALC_T_TMP, (void *) buf);
+ BIF_ERROR(BIF_P, BADARG);
+
+ }
+
/**********************************************************************/
/* convert a float to a list of ascii characters */
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index e313188901..aa6105de73 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -561,6 +561,10 @@ bif erlang:prepare_loading/2
bif erlang:finish_loading/1
bif erlang:insert_element/3
bif erlang:delete_element/2
+bif erlang:binary_to_integer/1
+bif erlang:binary_to_integer/2
+bif erlang:integer_to_binary/1
+bif erlang:list_to_integer/2
#
# Obsolete
diff --git a/erts/emulator/beam/big.c b/erts/emulator/beam/big.c
index 5a5b162b9c..acfcc845e4 100644
--- a/erts/emulator/beam/big.c
+++ b/erts/emulator/beam/big.c
@@ -1674,26 +1674,26 @@ int big_decimal_estimate(Wterm x)
** Convert a bignum into a string of decimal numbers
*/
-static void write_big(Wterm x, void (*write_func)(void *, char), void *arg)
+static Uint write_big(Wterm x, void (*write_func)(void *, char), void *arg)
{
Eterm* xp = big_val(x);
ErtsDigit* dx = BIG_V(xp);
dsize_t xl = BIG_SIZE(xp);
short sign = BIG_SIGN(xp);
ErtsDigit rem;
+ Uint n = 0;
if (xl == 1 && *dx < D_DECIMAL_BASE) {
rem = *dx;
- if (rem == 0)
- (*write_func)(arg, '0');
- else {
+ if (rem == 0) {
+ (*write_func)(arg, '0'); n++;
+ } else {
while(rem) {
- (*write_func)(arg, (rem % 10) + '0');
+ (*write_func)(arg, (rem % 10) + '0'); n++;
rem /= 10;
}
}
- }
- else {
+ } else {
ErtsDigit* tmp = (ErtsDigit*) erts_alloc(ERTS_ALC_T_TMP,
sizeof(ErtsDigit)*xl);
dsize_t tmpl = xl;
@@ -1704,15 +1704,14 @@ static void write_big(Wterm x, void (*write_func)(void *, char), void *arg)
tmpl = D_div(tmp, tmpl, D_DECIMAL_BASE, tmp, &rem);
if (tmpl == 1 && *tmp == 0) {
while(rem) {
- (*write_func)(arg, (rem % 10)+'0');
+ (*write_func)(arg, (rem % 10)+'0'); n++;
rem /= 10;
}
break;
- }
- else {
+ } else {
int i = D_DECIMAL_EXP;
while(i--) {
- (*write_func)(arg, (rem % 10)+'0');
+ (*write_func)(arg, (rem % 10)+'0'); n++;
rem /= 10;
}
}
@@ -1720,8 +1719,10 @@ static void write_big(Wterm x, void (*write_func)(void *, char), void *arg)
erts_free(ERTS_ALC_T_TMP, (void *) tmp);
}
- if (sign)
- (*write_func)(arg, '-');
+ if (sign) {
+ (*write_func)(arg, '-'); n++;
+ }
+ return n;
}
struct big_list__ {
@@ -1762,6 +1763,20 @@ char *erts_big_to_string(Wterm x, char *buf, Uint buf_sz)
return big_str;
}
+/* Bignum to binary bytes
+ * e.g. 1 bsl 64 -> "18446744073709551616"
+ */
+
+Uint erts_big_to_binary_bytes(Eterm x, char *buf, Uint buf_sz)
+{
+ char *big_str = buf + buf_sz;
+ Uint n;
+ n = write_big(x, write_string, (void *) &big_str);
+ ASSERT(buf <= big_str && big_str <= buf + buf_sz);
+ return n;
+}
+
+
/*
** Normalize a bignum given thing pointer length in digits and a sign
** patch zero if odd length
@@ -2467,3 +2482,209 @@ int term_equals_2pow32(Eterm x)
return 0;
}
}
+
+
+#define IS_VALID_CHARACTER(CHAR,BASE) \
+ (CHAR < '0' \
+ || (CHAR > ('0' + BASE - 1) \
+ && !(BASE > 10 \
+ && ((CHAR >= 'a' && CHAR < ('a' + BASE - 10)) \
+ || (CHAR >= 'A' && CHAR < ('A' + BASE - 10))))))
+#define CHARACTER_FROM_BASE(CHAR) \
+ ((CHAR <= '9') ? CHAR - '0' : 10 + ((CHAR <= 'Z') ? CHAR - 'A' : CHAR - 'a'))
+#define D_BASE_EXP(BASE) (d_base_exp_lookup[BASE-2])
+#define D_BASE_BASE(BASE) (d_base_base_lookup[BASE-2])
+#define LG2_LOOKUP(BASE) (lg2_lookup[base-2])
+
+/*
+ * for i in 2..64 do
+ * lg2_lookup[i-2] = log2(i)
+ * end
+ * How many bits are needed to store string of size n
+ */
+const double lg2_lookup[] = { 1.0, 1.58496, 2, 2.32193, 2.58496, 2.80735, 3.0,
+ 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.80735, 3.90689, 4.0,
+ 4.08746, 4.16993, 4.24793, 4.32193, 4.39232, 4.45943, 4.52356, 4.58496,
+ 4.64386, 4.70044, 4.75489, 4.80735, 4.85798, 4.90689, 4.9542, 5.0,
+ 5.04439, 5.08746, 5.12928, 5.16993, 5.20945, 5.24793, 5.2854, 5.32193,
+ 5.35755, 5.39232, 5.42626, 5.45943, 5.49185, 5.52356, 5.55459, 5.58496,
+ 5.61471, 5.64386, 5.67243, 5.70044, 5.72792, 5.75489, 5.78136, 5.80735,
+ 5.83289, 5.85798, 5.88264, 5.90689, 5.93074, 5.9542, 5.97728, 6.0 };
+
+/*
+ * for i in 2..64 do
+ * d_base_exp_lookup[i-2] = 31 / lg2_lookup[i-2];
+ * end
+ * How many characters can fit in 31 bits
+ */
+const byte d_base_exp_lookup[] = { 31, 19, 15, 13, 11, 11, 10, 9, 9, 8, 8, 8, 8,
+ 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 5, 5 };
+
+/*
+ * for i in 2..64 do
+ * d_base_base_lookup[i-2] = pow(i,d_base_exp_lookup[i-2]);
+ * end
+ * How much can the characters which fit in 31 bit represent
+ */
+const Uint d_base_base_lookup[] = { 2147483648, 1162261467, 1073741824,
+ 1220703125, 362797056, 1977326743, 1073741824, 387420489, 1000000000,
+ 214358881, 429981696, 815730721, 1475789056, 170859375, 268435456,
+ 410338673, 612220032, 893871739, 1280000000, 1801088541, 113379904,
+ 148035889, 191102976, 244140625, 308915776, 387420489, 481890304,
+ 594823321, 729000000, 887503681, 1073741824, 1291467969, 1544804416,
+ 1838265625, 60466176, 69343957, 79235168, 90224199, 102400000,
+ 115856201, 130691232, 147008443, 164916224, 184528125, 205962976,
+ 229345007, 254803968, 282475249, 312500000, 345025251, 380204032,
+ 418195493, 459165024, 503284375, 550731776, 601692057, 656356768,
+ 714924299, 777600000, 844596301, 916132832, 992436543, 1073741824 };
+
+Eterm erts_chars_to_integer(Process *BIF_P, char *bytes,
+ Uint size, const int base) {
+ Eterm res;
+ Sint i = 0;
+ int n = 0;
+ int neg = 0;
+ byte b;
+ Eterm *hp, *hp_end;
+ int m;
+ int lg2;
+
+ if (size == 0)
+ goto bytebuf_to_integer_1_error;
+
+ if (bytes[0] == '-') {
+ neg = 1;
+ bytes++;
+ size--;
+
+ } else if (bytes[0] == '+') {
+ bytes++;
+ size--;
+ }
+
+ if (size < SMALL_DIGITS && base <= 10) {
+ /* *
+ * Take shortcut if we know that all chars are '0' < b < '9' and
+ * fit in a small. This improves speed by about 10% over the generic
+ * small case.
+ * */
+ while (size--) {
+ b = *bytes++;
+
+ if (b < '0' || b > ('0'+base-1))
+ goto bytebuf_to_integer_1_error;
+
+ i = i * base + b - '0';
+ }
+
+ if (neg)
+ i = -i;
+ res = make_small(i);
+ goto bytebuf_to_integer_1_done;
+ }
+
+ /*
+ * Calculate the maximum number of bits which will
+ * be needed to represent the binary
+ */
+ lg2 = ((size+2)*LG2_LOOKUP(base)+1);
+
+ if (lg2 < SMALL_BITS) {
+ /* Take shortcut if we know it will fit in a small.
+ * This improves speed by about 30%.
+ */
+ while (size) {
+ b = *bytes++;
+ size--;
+
+ if (IS_VALID_CHARACTER(b,base))
+ goto bytebuf_to_integer_1_error;
+
+ i = i * base + CHARACTER_FROM_BASE(b);
+
+ }
+
+ if (neg)
+ i = -i;
+ res = make_small(i);
+ goto bytebuf_to_integer_1_done;
+
+ }
+
+ /* Start calculating bignum */
+ m = (lg2 + D_EXP-1)/D_EXP;
+ m = BIG_NEED_SIZE(m);
+
+ hp = HAlloc(BIF_P, m);
+ hp_end = hp + m;
+
+ if ((i = (size % D_BASE_EXP(base))) == 0)
+ i = D_BASE_EXP(base);
+
+ n = size - i;
+ m = 0;
+
+ while (i--) {
+ b = *bytes++;
+
+ if (IS_VALID_CHARACTER(b,base)) {
+ HRelease(BIF_P, hp_end, hp);
+ goto bytebuf_to_integer_1_error;
+ }
+
+ m = base * m + CHARACTER_FROM_BASE(b);
+ }
+
+ res = small_to_big(m, hp);
+
+ while (n) {
+ i = D_BASE_EXP(base);
+ n -= D_BASE_EXP(base);
+ m = 0;
+ while (i--) {
+ b = *bytes++;
+
+ if (IS_VALID_CHARACTER(b,base)) {
+ HRelease(BIF_P, hp_end, hp);
+ goto bytebuf_to_integer_1_error;
+ }
+
+ m = base * m + CHARACTER_FROM_BASE(b);
+ }
+ if (is_small(res)) {
+ res = small_to_big(signed_val(res), hp);
+ }
+ res = big_times_small(res, D_BASE_BASE(base), hp);
+ if (is_small(res)) {
+ res = small_to_big(signed_val(res), hp);
+ }
+ res = big_plus_small(res, m, hp);
+ }
+
+ if (is_big(res)) /* check if small */
+ res = big_plus_small(res, 0, hp); /* includes conversion to small */
+
+ if (neg) {
+ if (is_small(res))
+ res = make_small(-signed_val(res));
+ else {
+ Uint *big = big_val(res); /* point to thing */
+ *big = bignum_header_neg(*big);
+ }
+ }
+
+ if (is_big(res)) {
+ hp += (big_arity(res) + 1);
+ }
+ HRelease(BIF_P, hp_end, hp);
+ goto bytebuf_to_integer_1_done;
+
+bytebuf_to_integer_1_error:
+ return THE_NON_VALUE;
+
+bytebuf_to_integer_1_done:
+ return res;
+
+}
diff --git a/erts/emulator/beam/big.h b/erts/emulator/beam/big.h
index 7eb1e5afe2..c74283b9e5 100644
--- a/erts/emulator/beam/big.h
+++ b/erts/emulator/beam/big.h
@@ -117,6 +117,7 @@ typedef Uint dsize_t; /* Vector size type */
int big_decimal_estimate(Wterm);
Eterm erts_big_to_list(Eterm, Eterm**);
char *erts_big_to_string(Wterm x, char *buf, Uint buf_sz);
+Uint erts_big_to_binary_bytes(Eterm x, char *buf, Uint buf_sz);
Eterm small_times(Sint, Sint, Eterm*);
@@ -165,5 +166,7 @@ int term_equals_2pow32(Eterm);
Eterm erts_uint64_to_big(Uint64, Eterm **);
Eterm erts_sint64_to_big(Sint64, Eterm **);
+Eterm erts_chars_to_integer(Process *, char*, Uint, const int);
+
#endif
diff --git a/erts/emulator/beam/binary.c b/erts/emulator/beam/binary.c
index dad13f1067..33abac2f3d 100644
--- a/erts/emulator/beam/binary.c
+++ b/erts/emulator/beam/binary.c
@@ -240,6 +240,98 @@ erts_bin_bytes_to_list(Eterm previous, Eterm* hp, byte* bytes, Uint size, Uint b
return previous;
}
+BIF_RETTYPE binary_to_integer_1(BIF_ALIST_1)
+{
+ byte *temp_alloc = NULL;
+ char *bytes;
+ Uint size;
+ Eterm res;
+
+ if ((bytes = (char*)erts_get_aligned_binary_bytes(BIF_ARG_1, &temp_alloc))
+ == NULL )
+ goto binary_to_integer_1_error;
+
+ size = binary_size(BIF_ARG_1);
+
+ if ((res = erts_chars_to_integer(BIF_P,bytes,size,10)) != THE_NON_VALUE) {
+ erts_free_aligned_binary_bytes(temp_alloc);
+ return res;
+ }
+
+ binary_to_integer_1_error:
+ erts_free_aligned_binary_bytes(temp_alloc);
+ BIF_ERROR(BIF_P, BADARG);
+}
+
+BIF_RETTYPE binary_to_integer_2(BIF_ALIST_2)
+{
+ byte *temp_alloc = NULL;
+ char *bytes;
+ Uint size;
+ int base;
+ Eterm res;
+
+ if (!is_small(BIF_ARG_2))
+ BIF_ERROR(BIF_P, BADARG);
+
+ base = signed_val(BIF_ARG_2);
+
+ if (base < 2 || base > 36)
+ BIF_ERROR(BIF_P, BADARG);
+
+ if ((bytes = (char*)erts_get_aligned_binary_bytes(BIF_ARG_1, &temp_alloc))
+ == NULL )
+ goto binary_to_integer_2_error;
+
+ size = binary_size(BIF_ARG_1);
+
+ if ((res = erts_chars_to_integer(BIF_P,bytes,size,base)) != THE_NON_VALUE) {
+ erts_free_aligned_binary_bytes(temp_alloc);
+ return res;
+ }
+
+ binary_to_integer_2_error:
+
+ erts_free_aligned_binary_bytes(temp_alloc);
+ BIF_ERROR(BIF_P, BADARG);
+
+}
+
+BIF_RETTYPE integer_to_binary_1(BIF_ALIST_1)
+{
+ Uint size;
+ Eterm res;
+
+ if (is_not_integer(BIF_ARG_1)) {
+ BIF_ERROR(BIF_P, BADARG);
+ }
+
+ if (is_small(BIF_ARG_1)) {
+ char *c;
+ struct Sint_buf ibuf;
+
+ /* Enhancement: If we can calculate the buffer size exactly
+ * we could avoid an unnecessary copy of buffers.
+ * Useful if size determination is faster than a copy.
+ */
+ c = Sint_to_buf(signed_val(BIF_ARG_1), &ibuf);
+ size = sys_strlen(c);
+ res = new_binary(BIF_P, (byte *)c, size);
+ } else {
+ byte* bytes;
+ Uint n = 0;
+
+ /* Here we also have multiple copies of buffers
+ * due to new_binary interface
+ */
+ size = big_decimal_estimate(BIF_ARG_1) - 1; /* remove null */
+ bytes = (byte*) erts_alloc(ERTS_ALC_T_TMP, sizeof(byte)*size);
+ n = erts_big_to_binary_bytes(BIF_ARG_1, (char *)bytes, size);
+ res = new_binary(BIF_P, bytes + size - n, n);
+ erts_free(ERTS_ALC_T_TMP, (void *) bytes);
+ }
+ BIF_RET(res);
+}
BIF_RETTYPE binary_to_list_1(BIF_ALIST_1)
{