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
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.
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.
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
32 ;; Generate approximations of 10^k.
34 (module gen-ten-powers
35 (static (class Cached-Fast
42 ;;----------------bignum shifts -----------------------------------------------
43 (define (bit-lshbx::bignum x::bignum by::bint)
46 (*bx x (exptbx #z2 (fixnum->bignum by)))))
48 (define (bit-rshbx::bignum x::bignum by::bint)
51 (/bx x (exptbx #z2 (fixnum->bignum by)))))
53 ;;----------------the actual power generation -------------------------------
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))
63 ;; with the -1 it will only round up if the cut off part is
66 (-fx (+fx e nb-bits) 1))
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)
77 (round-n-cut n (+fx e 1) nb-bits))))
79 (define (rounded-/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))
86 (+bx (/bx tmp #z2) #z1))))))
88 (define (generate-powers from to mantissa-size)
89 (let* ((nb-bits mantissa-size)
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) ==
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.
110 (vector-set! vec (-fx offset i)
111 (instantiate::Cached-Fast
112 (v (rounded-/bx two^e ten^i))
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
122 (n (bit-lshbx #z1 (-fx nb-bits 1)))
125 (receive (cut e exact?)
126 (round-n-cut n e nb-bits)
127 (vector-set! vec (+fx i offset)
128 (instantiate::Cached-Fast
132 (loop (+fx i 1) (*bx n #z10) e))))
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"
149 (define (print-powers-reduced n)
150 (print "static const " struct-type " " cache-name
158 ((>= i (vector-length powers))
160 (print "static const int " max-distance-name "(" n ") = "
162 (print "// nb elements (" n "): " nb-elements))
164 (let* ((power (vector-ref powers i))
165 (e (Cached-Fast-e power)))
166 (display-power power (+ i from))
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:")
178 (apply string-append (map (lambda (str)
179 (string-append " " str))
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")
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) ";"))
227 ;;----------------main --------------------------------------------------------
228 (define *main-args* #f)
229 (define *mantissa-size* #f)
235 (define (my-main args)
236 (set! *main-args* args)
237 (args-parse (cdr args)
239 (("?") (args-parse-usage #f))
240 ((("-h" "--help") (help "?, -h, --help" "This help message"))
241 (args-parse-usage #f))
243 (("-o" ?file (help "The output 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)))
254 (print "Illegal argument `" else "'. Usage:")
255 (args-parse-usage #f)))
257 (error "generate-ten-powers"
261 (error "generate-ten-powers"
264 (when (not *mantissa-size*)
265 (error "generate-ten-powers"
266 "Missing mantissa size"
268 (when (not (memv *round* '(up down round)))
269 (error "generate-ten-powers"
270 "Missing round-method"
273 (let ((dividers (generate-powers *from* *to* *mantissa-size*))
275 (current-output-port)
276 (open-output-file *dest*))))
278 (with-output-to-port p
280 (print-c dividers *from* *to*
281 "GRISU_CACHE_STRUCT" "GRISU_CACHE_NAME"
282 "GRISU_CACHE_MAX_DISTANCE" "GRISU_CACHE_OFFSET"
286 (close-output-port p)))))