Home | History | Annotate | Download | only in tools
      1 ;; Copyright 2010 the V8 project authors. All rights reserved.
      2 ;; Redistribution and use in source and binary forms, with or without
      3 ;; modification, are permitted provided that the following conditions are
      4 ;; met:
      5 ;;
      6 ;;     * Redistributions of source code must retain the above copyright
      7 ;;       notice, this list of conditions and the following disclaimer.
      8 ;;     * Redistributions in binary form must reproduce the above
      9 ;;       copyright notice, this list of conditions and the following
     10 ;;       disclaimer in the documentation and/or other materials provided
     11 ;;       with the distribution.
     12 ;;     * Neither the name of Google Inc. nor the names of its
     13 ;;       contributors may be used to endorse or promote products derived
     14 ;;       from this software without specific prior written permission.
     15 ;;
     16 ;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 ;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 ;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 ;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 ;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 ;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 ;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 ;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 ;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 ;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 ;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 ;; This is a Scheme script for the Bigloo compiler. Bigloo must be compiled with
     29 ;; support for bignums. The compilation of the script can be done as follows:
     30 ;;   bigloo -static-bigloo -o generate-ten-powers generate-ten-powers.scm
     31 ;;
     32 ;; Generate approximations of 10^k.
     33 
     34 (module gen-ten-powers
     35    (static (class Cached-Fast
     36 	      v::bignum
     37 	      e::bint
     38 	      exact?::bool))
     39    (main my-main))
     40 
     41 
     42 ;;----------------bignum shifts -----------------------------------------------
     43 (define (bit-lshbx::bignum x::bignum by::bint)
     44    (if ( by 0)
     45        #z0
     46        (*bx x (exptbx #z2 (fixnum->bignum by)))))
     47 
     48 (define (bit-rshbx::bignum x::bignum by::bint)
     49    (if ( by 0)
     50        #z0
     51        (/bx x (exptbx #z2 (fixnum->bignum by)))))
     52 
     53 ;;----------------the actual power generation -------------------------------
     54 
     55 ;; e should be an indication. it might be too small.
     56 (define (round-n-cut n e nb-bits)
     57    (define max-container (- (bit-lshbx #z1 nb-bits) 1))
     58    (define (round n)
     59       (case *round*
     60 	 ((down) n)
     61 	 ((up)
     62 	  (+bx n
     63 	       ;; with the -1 it will only round up if the cut off part is
     64 	       ;; non-zero
     65 	       (-bx (bit-lshbx #z1
     66 			       (-fx (+fx e nb-bits) 1))
     67 		    #z1)))
     68 	 ((round)
     69 	  (+bx n
     70 	       (bit-lshbx #z1
     71 			  (-fx (+fx e nb-bits) 2))))))
     72    (let* ((shift (-fx (+fx e nb-bits) 1))
     73 	  (cut (bit-rshbx (round n) shift))
     74 	  (exact? (=bx n (bit-lshbx cut shift))))
     75       (if (<=bx cut max-container)
     76 	  (values cut e exact?)
     77 	  (round-n-cut n (+fx e 1) nb-bits))))
     78 
     79 (define (rounded-/bx x y)
     80    (case *round*
     81       ((down)  (/bx x y))
     82       ((up)    (+bx (/bx x y) #z1))
     83       ((round) (let ((tmp (/bx (*bx #z2 x) y)))
     84 		  (if (zerobx? (remainderbx tmp #z2))
     85 		      (/bx tmp #z2)
     86 		      (+bx (/bx tmp #z2) #z1))))))
     87 
     88 (define (generate-powers from to mantissa-size)
     89    (let* ((nb-bits mantissa-size)
     90 	  (offset (- from))
     91 	  (nb-elements (+ (- from) to 1))
     92 	  (vec (make-vector nb-elements))
     93 	  (max-container (- (bit-lshbx #z1 nb-bits) 1)))
     94       ;; the negative ones. 10^-1, 10^-2, etc.
     95       ;; We already know, that we can't be exact, so exact? will always be #f.
     96       ;; Basically we will have a ten^i that we will *10 at each iteration. We
     97       ;; want to create the matissa of 1/ten^i. However the mantissa must be
     98       ;; normalized (start with a 1). -> we have to shift the number.
     99       ;; We shift by multiplying with two^e. -> We encode two^e*(1/ten^i) ==
    100       ;;  two^e/ten^i.
    101       (let loop ((i 1)
    102 		 (ten^i #z10)
    103 		 (two^e #z1)
    104 		 (e 0))
    105 	 (unless (< (- i) from)
    106 	    (if (>bx (/bx (*bx #z2 two^e) ten^i) max-container)
    107 		;; another shift would make the number too big. We are
    108 		;; hence normalized now.
    109 		(begin
    110 		   (vector-set! vec (-fx offset i)
    111 				(instantiate::Cached-Fast
    112 				   (v (rounded-/bx two^e ten^i))
    113 				   (e (negfx e))
    114 				   (exact? #f)))
    115 		   (loop (+fx i 1) (*bx ten^i #z10) two^e e))
    116 		(loop i ten^i (bit-lshbx two^e 1) (+fx e 1)))))
    117       ;; the positive ones 10^0, 10^1, etc.
    118       ;; start with 1.0. mantissa: 10...0 (1 followed by nb-bits-1 bits)
    119       ;;      -> e = -(nb-bits-1)
    120       ;; exact? is true when the container can still hold the complete 10^i
    121       (let loop ((i 0)
    122 		 (n (bit-lshbx #z1 (-fx nb-bits 1)))
    123 		 (e (-fx 1 nb-bits)))
    124 	 (when (<= i to)
    125 	    (receive (cut e exact?)
    126 	       (round-n-cut n e nb-bits)
    127 	       (vector-set! vec (+fx i offset)
    128 			    (instantiate::Cached-Fast
    129 			       (v cut)
    130 			       (e e)
    131 			       (exact? exact?)))
    132 	       (loop (+fx i 1) (*bx n #z10) e))))
    133       vec))
    134 
    135 (define (print-c powers from to struct-type
    136 		 cache-name max-distance-name offset-name macro64)
    137    (define (display-power power k)
    138       (with-access::Cached-Fast power (v e exact?)
    139 	 (let ((tmp-p (open-output-string)))
    140 	    ;; really hackish way of getting the digits
    141 	    (display (format "~x" v) tmp-p)
    142 	    (let ((str (close-output-port tmp-p)))
    143 	       (printf "  {~a(0x~a, ~a), ~a, ~a},\n"
    144 		       macro64
    145 		       (substring str 0 8)
    146 		       (substring str 8 16)
    147 		       e
    148 		       k)))))
    149    (define (print-powers-reduced n)
    150       (print "static const " struct-type " " cache-name
    151 	     "(" n ")"
    152 	     "[] = {")
    153       (let loop ((i 0)
    154 		 (nb-elements 0)
    155 		 (last-e 0)
    156 		 (max-distance 0))
    157 	 (cond
    158 	    ((>= i (vector-length powers))
    159 	     (print "  };")
    160 	     (print "static const int " max-distance-name "(" n ") = "
    161 		 max-distance ";")
    162 	     (print "// nb elements (" n "): " nb-elements))
    163 	    (else
    164 	     (let* ((power (vector-ref powers i))
    165 		    (e (Cached-Fast-e power)))
    166 	     (display-power power (+ i from))
    167 	     (loop (+ i n)
    168 		   (+ nb-elements 1)
    169 		   e
    170 		   (cond
    171 		      ((=fx i 0) max-distance)
    172 		      ((> (- e last-e) max-distance) (- e last-e))
    173 		      (else max-distance))))))))
    174    (print "// Copyright 2010 the V8 project authors. All rights reserved.")
    175    (print "// ------------ GENERATED FILE ----------------")
    176    (print "// command used:")
    177    (print "// "
    178 	  (apply string-append (map (lambda (str)
    179 				       (string-append " " str))
    180 				    *main-args*))
    181 	  "  // NOLINT")
    182    (print)
    183    (print
    184     "// This file is intended to be included inside another .h or .cc files\n"
    185     "// with the following defines set:\n"
    186     "//  GRISU_CACHE_STRUCT: should expand to the name of a struct that will\n"
    187     "//   hold the cached powers of ten. Each entry will hold a 64-bit\n"
    188     "//   significand, a 16-bit signed binary exponent, and a 16-bit\n"
    189     "//   signed decimal exponent. Each entry will be constructed as follows:\n"
    190     "//      { significand, binary_exponent, decimal_exponent }.\n"
    191     "//  GRISU_CACHE_NAME(i): generates the name for the different caches.\n"
    192     "//   The parameter i will be a number in the range 1-20. A cache will\n"
    193     "//   hold every i'th element of a full cache. GRISU_CACHE_NAME(1) will\n"
    194     "//   thus hold all elements. The higher i the fewer elements it has.\n"
    195     "//   Ideally the user should only reference one cache and let the\n"
    196     "//   compiler remove the unused ones.\n"
    197     "//  GRISU_CACHE_MAX_DISTANCE(i): generates the name for the maximum\n"
    198     "//   binary exponent distance between all elements of a given cache.\n"
    199     "//  GRISU_CACHE_OFFSET: is used as variable name for the decimal\n"
    200     "//   exponent offset. It is equal to -cache[0].decimal_exponent.\n"
    201     "//  GRISU_UINT64_C: used to construct 64-bit values in a platform\n"
    202     "//   independent way. In order to encode 0x123456789ABCDEF0 the macro\n"
    203     "//   will be invoked as follows: GRISU_UINT64_C(0x12345678,9ABCDEF0).\n")
    204    (print)
    205    (print-powers-reduced 1)
    206    (print-powers-reduced 2)
    207    (print-powers-reduced 3)
    208    (print-powers-reduced 4)
    209    (print-powers-reduced 5)
    210    (print-powers-reduced 6)
    211    (print-powers-reduced 7)
    212    (print-powers-reduced 8)
    213    (print-powers-reduced 9)
    214    (print-powers-reduced 10)
    215    (print-powers-reduced 11)
    216    (print-powers-reduced 12)
    217    (print-powers-reduced 13)
    218    (print-powers-reduced 14)
    219    (print-powers-reduced 15)
    220    (print-powers-reduced 16)
    221    (print-powers-reduced 17)
    222    (print-powers-reduced 18)
    223    (print-powers-reduced 19)
    224    (print-powers-reduced 20)
    225    (print "static const int GRISU_CACHE_OFFSET = " (- from) ";"))
    226 
    227 ;;----------------main --------------------------------------------------------
    228 (define *main-args* #f)
    229 (define *mantissa-size* #f)
    230 (define *dest* #f)
    231 (define *round* #f)
    232 (define *from* #f)
    233 (define *to* #f)
    234 
    235 (define (my-main args)
    236    (set! *main-args* args)
    237    (args-parse (cdr args)
    238       (section "Help")
    239       (("?") (args-parse-usage #f))
    240       ((("-h" "--help") (help "?, -h, --help" "This help message"))
    241        (args-parse-usage #f))
    242       (section "Misc")
    243       (("-o" ?file (help "The output file"))
    244        (set! *dest* file))
    245       (("--mantissa-size" ?size (help "Container-size in bits"))
    246        (set! *mantissa-size* (string->number size)))
    247       (("--round" ?direction (help "Round bignums (down, round or up)"))
    248        (set! *round* (string->symbol direction)))
    249       (("--from" ?from (help "start at 10^from"))
    250        (set! *from* (string->number from)))
    251       (("--to" ?to (help "go up to 10^to"))
    252        (set! *to* (string->number to)))
    253       (else
    254        (print "Illegal argument `" else "'. Usage:")
    255        (args-parse-usage #f)))
    256    (when (not *from*)
    257       (error "generate-ten-powers"
    258 	     "Missing from"
    259 	     #f))
    260    (when (not *to*)
    261       (error "generate-ten-powers"
    262 	     "Missing to"
    263 	     #f))
    264    (when (not *mantissa-size*)
    265       (error "generate-ten-powers"
    266 	     "Missing mantissa size"
    267 	     #f))
    268    (when (not (memv *round* '(up down round)))
    269       (error "generate-ten-powers"
    270 	     "Missing round-method"
    271 	     *round*))
    272 
    273    (let ((dividers (generate-powers *from* *to* *mantissa-size*))
    274 	 (p (if (not *dest*)
    275 		(current-output-port)
    276 		(open-output-file *dest*))))
    277       (unwind-protect
    278 	 (with-output-to-port p
    279 	    (lambda ()
    280 	       (print-c dividers *from* *to*
    281 			"GRISU_CACHE_STRUCT" "GRISU_CACHE_NAME"
    282 			"GRISU_CACHE_MAX_DISTANCE" "GRISU_CACHE_OFFSET"
    283 			"GRISU_UINT64_C"
    284 			)))
    285 	 (if *dest*
    286 	     (close-output-port p)))))
    287