Changeset 31353 in project


Ignore:
Timestamp:
09/09/14 21:29:09 (5 years ago)
Author:
sjamaan
Message:

numbers: Convert bignum->string printer to core naming conventions. TODO: Make it perform acceptably in the ~same way as we made string->bignum reading faster.

Location:
release/4/numbers/trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • release/4/numbers/trunk/numbers-c.c

    r31352 r31353  
    14331433}
    14341434
    1435 #define BIGNUM_STR_BLOCK_SIZE 8
    1436 
    1437 /*
    1438  * Contains s48_bignum_to_digit_stream.  We may want to separate that out
    1439  * again in case of huge numbers; it may be more efficient to write
    1440  * those straight to files without going through the string conversion.
    1441  */
    1442 static void
    1443 big_to_string(C_word c, C_word self, C_word k, C_word value, C_word radix)
    1444 {
    1445   char *buf, *index;
    1446   C_word len, counter=0;
    1447   char *characters = "0123456789abcdef";
    1448   C_word *tmp, ret;
    1449   bignum_type bignum;
    1450 
    1451   bignum = big_of(value);
    1452   len = BIGNUM_STR_BLOCK_SIZE;
    1453   buf = C_malloc(len);
    1454   if (buf == NULL) {
    1455     fprintf(stderr, "out of memory - can not allocate string");
    1456     exit(EXIT_FAILURE);
    1457   }
    1458   index = buf + len - 1;
    1459 
    1460   if (BIGNUM_NEGATIVE_P(bignum)) {
    1461     *index-- = '-';
    1462     counter++;
    1463   }
    1464 
    1465   radix = C_unfix(radix);
    1466  
    1467   assert((radix > 1) && (radix <= BIGNUM_RADIX_ROOT));
    1468   if (! (BIGNUM_ZERO_P (bignum)))
    1469     {
    1470       bignum_type working_copy = (bignum_copy (bignum));
    1471       bignum_digit_type * start = (BIGNUM_START_PTR (working_copy));
    1472       bignum_digit_type * scan = (start + (BIGNUM_LENGTH (working_copy)));
    1473       bignum_digit_type digit;
    1474       while (start < scan)
    1475         {
    1476           if ((scan[-1]) == 0) {
    1477             scan -= 1;
    1478           } else {
    1479             digit = bignum_destructive_scale_down (working_copy, radix);
    1480             *index-- = characters[digit];
    1481             if (++counter == len) {
    1482               char *newbuf;
    1483               newbuf = C_malloc(len + BIGNUM_STR_BLOCK_SIZE);
    1484               if (newbuf == NULL) {
    1485                 fprintf(stderr, "out of memory - can not allocate string");
    1486                 exit(EXIT_FAILURE);
    1487               }
    1488               C_memcpy(newbuf + BIGNUM_STR_BLOCK_SIZE, buf, len);
    1489               C_free(buf);
    1490               buf = newbuf;
    1491               index = newbuf + BIGNUM_STR_BLOCK_SIZE - 1;
    1492               len += BIGNUM_STR_BLOCK_SIZE;
    1493             }
    1494           }
    1495         }
    1496       BIGNUM_DEALLOCATE (working_copy);
    1497     }
    1498 
    1499   if (BIGNUM_NEGATIVE_P(bignum))
    1500     *index-- = '-';
    1501 
    1502   tmp = C_alloc(C_SIZEOF_STRING(counter));
    1503   ret = C_string(&tmp, counter, index+1);
    1504   C_free(buf);
    1505   C_kontinue(k, ret);
    1506 }
    1507 
    15081435/**
    15091436 * Below you will find the functions that have been refactored to
     
    15291456static void bignum_times_bignum_unsigned_2(C_word c, C_word self, C_word result);
    15301457static void digits_to_integer_2(C_word c, C_word self, C_word result);
     1458static void bignum_to_digits_2(C_word c, C_word self, C_word working_copy);
    15311459static void flo_to_int_2(C_word c, C_word self, C_word result);
    15321460static C_word ilen(C_uword x);
     
    19611889  }
    19621890  return carry;
     1891}
     1892
     1893/* Given (denominator > 1), it is fairly easy to show that
     1894   quotient_high fits a bignum halfdigit, after which it is easy to
     1895   see that all digits fit a bignum full digit. */
     1896static C_word
     1897bignum_digits_destructive_scale_down(C_word *start, C_word *end, C_word denominator)
     1898{
     1899  C_word numerator, remainder = 0, digit, quotient_high, *scan = end;
     1900
     1901  assert((denominator > 1) && C_fitsinbignumhalfdigitp(denominator));
     1902  while (start <= scan) {
     1903    digit = *scan;
     1904    numerator = C_BIGNUM_DIGIT_COMBINE(remainder, C_BIGNUM_DIGIT_HI_HALF(digit));
     1905    quotient_high = (numerator / denominator);
     1906    numerator = C_BIGNUM_DIGIT_COMBINE(numerator % denominator,
     1907                                       C_BIGNUM_DIGIT_LO_HALF(digit));
     1908    (*scan--) = C_BIGNUM_DIGIT_COMBINE(quotient_high, numerator / denominator);
     1909    remainder = numerator % denominator;
     1910  }
     1911  return remainder;
    19631912}
    19641913
     
    22242173}
    22252174
     2175void C_ccall
     2176C_u_bignum_to_digits(C_word c, C_word self, C_word k, C_word value, C_word radix)
     2177{
     2178  /* This copies the bignum over into a working copy that can be mutated. */
     2179  C_word kab[C_SIZEOF_CLOSURE(4)], *ka = kab, k2, size,
     2180         negp = C_mk_bool(C_bignum_negativep(value));
     2181
     2182  k2 = C_closure(&ka, 4, (C_word)bignum_to_digits_2, k, value, radix);
     2183
     2184  size = C_fix(C_bignum_size(value));
     2185  C_allocate_bignum(3, (C_word)NULL, k2, size, negp, C_SCHEME_FALSE);
     2186}
     2187
     2188#define BIGNUM_STR_BLOCK_SIZE 8
     2189
     2190/* XXX FIXME TODO: This is ridiculously slow! */
     2191static void
     2192bignum_to_digits_2(C_word c, C_word self, C_word working_copy)
     2193{
     2194  C_word k = C_block_item(self, 1),
     2195         old_big = C_block_item(self, 2),
     2196         radix = C_unfix(C_block_item(self, 3)),
     2197         *start = C_bignum_digits(working_copy),
     2198         *scan = start + C_bignum_size(working_copy) - 1,
     2199         digit;
     2200  char *buf, *index;
     2201  C_word len, counter=0;
     2202  char *characters = "0123456789abcdef";
     2203  C_word *tmp, ret;
     2204
     2205  /* Copy the old bignum's digits as-is into our working copy */
     2206  C_memcpy(C_bignum_digits(working_copy), C_bignum_digits(old_big),
     2207           /* TODO: This is currently in bytes.  If we change the
     2208            * representation that needs to change!
     2209            * We subtract the size of the header, too.
     2210            */
     2211           C_header_size(C_internal_bignum(old_big)) - C_wordstobytes(1));
     2212
     2213  assert(radix > 1 && C_fitsinbignumhalfdigitp(radix));
     2214
     2215  len = BIGNUM_STR_BLOCK_SIZE;
     2216  buf = C_malloc(len);
     2217  if (buf == NULL) {
     2218    fprintf(stderr, "out of memory - can not allocate string");
     2219    exit(EXIT_FAILURE);
     2220  }
     2221  index = buf + len - 1;
     2222
     2223  if (C_bignum_negativep(working_copy)) {
     2224    *index-- = '-';
     2225    counter++;
     2226  }
     2227
     2228  while (start <= scan) {
     2229    if (*scan == 0) {
     2230      scan--;
     2231    } else {
     2232      digit = bignum_digits_destructive_scale_down(start, scan, radix);
     2233      *index-- = characters[digit];
     2234      if (++counter == len) {
     2235        char *newbuf;
     2236        newbuf = C_malloc(len + BIGNUM_STR_BLOCK_SIZE);
     2237        if (newbuf == NULL) {
     2238          fprintf(stderr, "out of memory - can not allocate string");
     2239          exit(EXIT_FAILURE);
     2240        }
     2241        C_memcpy(newbuf + BIGNUM_STR_BLOCK_SIZE, buf, len);
     2242        C_free(buf);
     2243        buf = newbuf;
     2244        index = newbuf + BIGNUM_STR_BLOCK_SIZE - 1;
     2245        len += BIGNUM_STR_BLOCK_SIZE;
     2246      }
     2247    }
     2248  }
     2249
     2250  if (C_bignum_negativep(working_copy))
     2251    *index-- = '-';
     2252
     2253  /* XXX TODO: Check if memory is available with C_demand() */
     2254  tmp = C_alloc(C_SIZEOF_STRING(counter));
     2255  ret = C_string(&tmp, counter, index+1);
     2256  C_free(buf);
     2257  C_kontinue(k, ret);
     2258}
     2259
    22262260C_word
    22272261C_a_u_i_big_to_flo(C_word **p, C_word n, C_word bignum)
  • release/4/numbers/trunk/numbers-c.h

    r31352 r31353  
    239239
    240240void C_ccall C_digits_to_integer(C_word c, C_word self, C_word k, C_word n, C_word start, C_word end, C_word radix, C_word negp);
     241void C_ccall C_u_bignum_to_digits(C_word c, C_word self, C_word k, C_word value, C_word radix);
    241242C_word C_a_u_i_big_to_flo(C_word **p, C_word n, C_word bignum);
    242243void C_ccall C_u_flo_to_int(C_word c, C_word self, C_word k, C_word x);
  • release/4/numbers/trunk/numbers.scm

    r31352 r31353  
    193193(define number->string-0 (##core#primitive "C_number_to_string"))
    194194
    195 (define %big->string (##core#primitive "big_to_string"))
     195(define %big->string (##core#primitive "C_u_bignum_to_digits"))
    196196(define %digits->integer (##core#primitive "C_digits_to_integer"))
    197197
Note: See TracChangeset for help on using the changeset viewer.