tools/generate-ten-powers.scm - v8/v8 - Git at Google

 ;; Copyright 2010 the V8 project authors. All rights reserved.
 ;; Redistribution and use in source and binary forms, with or without
 ;; modification, are permitted provided that the following conditions are
 ;; met:
 ;;
 ;;     * Redistributions of source code must retain the above copyright
 ;;       notice, this list of conditions and the following disclaimer.
 ;;     * Redistributions in binary form must reproduce the above
 ;;       copyright notice, this list of conditions and the following
 ;;       disclaimer in the documentation and/or other materials provided
 ;;       with the distribution.
 ;;     * Neither the name of Google Inc. nor the names of its
 ;;       contributors may be used to endorse or promote products derived
 ;;       from this software without specific prior written permission.
 ;;
 ;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 ;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 ;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 ;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 ;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 ;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 ;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 ;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 ;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 ;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 ;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 ;; This is a Scheme script for the Bigloo compiler. Bigloo must be compiled with
 ;; support for bignums. The compilation of the script can be done as follows:
 ;;   bigloo -static-bigloo -o generate-ten-powers generate-ten-powers.scm
 ;;
 ;; Generate approximations of 10^k.

 (module gen-ten-powers
    (static (class Cached-Fast
 	      v::bignum
 	      e::bint
 	      exact?::bool))
    (main my-main))


 ;;----------------bignum shifts -----------------------------------------------
 (define (bit-lshbx::bignum x::bignum by::bint)
    (if (<fx by 0)
        #z0
        (*bx x (exptbx #z2 (fixnum->bignum by)))))

 (define (bit-rshbx::bignum x::bignum by::bint)
    (if (<fx by 0)
        #z0
        (/bx x (exptbx #z2 (fixnum->bignum by)))))

 ;;----------------the actual power generation -------------------------------

 ;; e should be an indication. it might be too small.
 (define (round-n-cut n e nb-bits)
    (define max-container (- (bit-lshbx #z1 nb-bits) 1))
    (define (round n)
       (case *round*
 	 ((down) n)
 	 ((up)
 	  (+bx n
 	       ;; with the -1 it will only round up if the cut off part is
 	       ;; non-zero
 	       (-bx (bit-lshbx #z1
 			       (-fx (+fx e nb-bits) 1))
 		    #z1)))
 	 ((round)
 	  (+bx n
 	       (bit-lshbx #z1
 			  (-fx (+fx e nb-bits) 2))))))
    (let* ((shift (-fx (+fx e nb-bits) 1))
 	  (cut (bit-rshbx (round n) shift))
 	  (exact? (=bx n (bit-lshbx cut shift))))
       (if (<=bx cut max-container)
 	  (values cut e exact?)
 	  (round-n-cut n (+fx e 1) nb-bits))))

 (define (rounded-/bx x y)
    (case *round*
       ((down)  (/bx x y))
       ((up)    (+bx (/bx x y) #z1))
       ((round) (let ((tmp (/bx (*bx #z2 x) y)))
 		  (if (zerobx? (remainderbx tmp #z2))
 		      (/bx tmp #z2)
 		      (+bx (/bx tmp #z2) #z1))))))

 (define (generate-powers from to mantissa-size)
    (let* ((nb-bits mantissa-size)
 	  (offset (- from))
 	  (nb-elements (+ (- from) to 1))
 	  (vec (make-vector nb-elements))
 	  (max-container (- (bit-lshbx #z1 nb-bits) 1)))
       ;; the negative ones. 10^-1, 10^-2, etc.
       ;; We already know, that we can't be exact, so exact? will always be #f.
       ;; Basically we will have a ten^i that we will *10 at each iteration. We
       ;; want to create the matissa of 1/ten^i. However the mantissa must be
       ;; normalized (start with a 1). -> we have to shift the number.
       ;; We shift by multiplying with two^e. -> We encode two^e*(1/ten^i) ==
       ;;  two^e/ten^i.
       (let loop ((i 1)
 		 (ten^i #z10)
 		 (two^e #z1)
 		 (e 0))
 	 (unless (< (- i) from)
 	    (if (>bx (/bx (*bx #z2 two^e) ten^i) max-container)
 		;; another shift would make the number too big. We are
 		;; hence normalized now.
 		(begin
 		   (vector-set! vec (-fx offset i)
 				(instantiate::Cached-Fast
 				   (v (rounded-/bx two^e ten^i))
 				   (e (negfx e))
 				   (exact? #f)))
 		   (loop (+fx i 1) (*bx ten^i #z10) two^e e))
 		(loop i ten^i (bit-lshbx two^e 1) (+fx e 1)))))
       ;; the positive ones 10^0, 10^1, etc.
       ;; start with 1.0. mantissa: 10...0 (1 followed by nb-bits-1 bits)
       ;;      -> e = -(nb-bits-1)
       ;; exact? is true when the container can still hold the complete 10^i
       (let loop ((i 0)
 		 (n (bit-lshbx #z1 (-fx nb-bits 1)))
 		 (e (-fx 1 nb-bits)))
 	 (when (<= i to)
 	    (receive (cut e exact?)
 	       (round-n-cut n e nb-bits)
 	       (vector-set! vec (+fx i offset)
 			    (instantiate::Cached-Fast
 			       (v cut)
 			       (e e)
 			       (exact? exact?)))
 	       (loop (+fx i 1) (*bx n #z10) e))))
       vec))

 (define (print-c powers from to struct-type
 		 cache-name max-distance-name offset-name macro64)
    (define (display-power power k)
       (with-access::Cached-Fast power (v e exact?)
 	 (let ((tmp-p (open-output-string)))
 	    ;; really hackish way of getting the digits
 	    (display (format "~x" v) tmp-p)
 	    (let ((str (close-output-port tmp-p)))
 	       (printf "  {~a(0x~a, ~a), ~a, ~a},\n"
 		       macro64
 		       (substring str 0 8)
 		       (substring str 8 16)
 		       e
 		       k)))))
    (define (print-powers-reduced n)
       (print "static const " struct-type " " cache-name
 	     "(" n ")"
 	     "[] = {")
       (let loop ((i 0)
 		 (nb-elements 0)
 		 (last-e 0)
 		 (max-distance 0))
 	 (cond
 	    ((>= i (vector-length powers))
 	     (print "  };")
 	     (print "static const int " max-distance-name "(" n ") = "
 		 max-distance ";")
 	     (print "// nb elements (" n "): " nb-elements))
 	    (else
 	     (let* ((power (vector-ref powers i))
 		    (e (Cached-Fast-e power)))
 	     (display-power power (+ i from))
 	     (loop (+ i n)
 		   (+ nb-elements 1)
 		   e
 		   (cond
 		      ((=fx i 0) max-distance)
 		      ((> (- e last-e) max-distance) (- e last-e))
 		      (else max-distance))))))))
    (print "// Copyright 2010 the V8 project authors. All rights reserved.")
    (print "// ------------ GENERATED FILE ----------------")
    (print "// command used:")
    (print "// "
 	  (apply string-append (map (lambda (str)
 				       (string-append " " str))
 				    *main-args*))
 	  "  // NOLINT")
    (print)
    (print
     "// This file is intended to be included inside another .h or .cc files\n"
     "// with the following defines set:\n"
     "//  GRISU_CACHE_STRUCT: should expand to the name of a struct that will\n"
     "//   hold the cached powers of ten. Each entry will hold a 64-bit\n"
     "//   significand, a 16-bit signed binary exponent, and a 16-bit\n"
     "//   signed decimal exponent. Each entry will be constructed as follows:\n"
     "//      { significand, binary_exponent, decimal_exponent }.\n"
     "//  GRISU_CACHE_NAME(i): generates the name for the different caches.\n"
     "//   The parameter i will be a number in the range 1-20. A cache will\n"
     "//   hold every i'th element of a full cache. GRISU_CACHE_NAME(1) will\n"
     "//   thus hold all elements. The higher i the fewer elements it has.\n"
     "//   Ideally the user should only reference one cache and let the\n"
     "//   compiler remove the unused ones.\n"
     "//  GRISU_CACHE_MAX_DISTANCE(i): generates the name for the maximum\n"
     "//   binary exponent distance between all elements of a given cache.\n"
     "//  GRISU_CACHE_OFFSET: is used as variable name for the decimal\n"
     "//   exponent offset. It is equal to -cache[0].decimal_exponent.\n"
     "//  GRISU_UINT64_C: used to construct 64-bit values in a platform\n"
     "//   independent way. In order to encode 0x123456789ABCDEF0 the macro\n"
     "//   will be invoked as follows: GRISU_UINT64_C(0x12345678,9ABCDEF0).\n")
    (print)
    (print-powers-reduced 1)
    (print-powers-reduced 2)
    (print-powers-reduced 3)
    (print-powers-reduced 4)
    (print-powers-reduced 5)
    (print-powers-reduced 6)
    (print-powers-reduced 7)
    (print-powers-reduced 8)
    (print-powers-reduced 9)
    (print-powers-reduced 10)
    (print-powers-reduced 11)
    (print-powers-reduced 12)
    (print-powers-reduced 13)
    (print-powers-reduced 14)
    (print-powers-reduced 15)
    (print-powers-reduced 16)
    (print-powers-reduced 17)
    (print-powers-reduced 18)
    (print-powers-reduced 19)
    (print-powers-reduced 20)
    (print "static const int GRISU_CACHE_OFFSET = " (- from) ";"))

 ;;----------------main --------------------------------------------------------
 (define *main-args* #f)
 (define *mantissa-size* #f)
 (define *dest* #f)
 (define *round* #f)
 (define *from* #f)
 (define *to* #f)

 (define (my-main args)
    (set! *main-args* args)
    (args-parse (cdr args)
       (section "Help")
       (("?") (args-parse-usage #f))
       ((("-h" "--help") (help "?, -h, --help" "This help message"))
        (args-parse-usage #f))
       (section "Misc")
       (("-o" ?file (help "The output file"))
        (set! *dest* file))
       (("--mantissa-size" ?size (help "Container-size in bits"))
        (set! *mantissa-size* (string->number size)))
       (("--round" ?direction (help "Round bignums (down, round or up)"))
        (set! *round* (string->symbol direction)))
       (("--from" ?from (help "start at 10^from"))
        (set! *from* (string->number from)))
       (("--to" ?to (help "go up to 10^to"))
        (set! *to* (string->number to)))
       (else
        (print "Illegal argument `" else "'. Usage:")
        (args-parse-usage #f)))
    (when (not *from*)
       (error "generate-ten-powers"
 	     "Missing from"
 	     #f))
    (when (not *to*)
       (error "generate-ten-powers"
 	     "Missing to"
 	     #f))
    (when (not *mantissa-size*)
       (error "generate-ten-powers"
 	     "Missing mantissa size"
 	     #f))
    (when (not (memv *round* '(up down round)))
       (error "generate-ten-powers"
 	     "Missing round-method"
 	     *round*))

    (let ((dividers (generate-powers *from* *to* *mantissa-size*))
 	 (p (if (not *dest*)
 		(current-output-port)
 		(open-output-file *dest*))))
       (unwind-protect
 	 (with-output-to-port p
 	    (lambda ()
 	       (print-c dividers *from* *to*
 			"GRISU_CACHE_STRUCT" "GRISU_CACHE_NAME"
 			"GRISU_CACHE_MAX_DISTANCE" "GRISU_CACHE_OFFSET"
 			"GRISU_UINT64_C"
 			)))
 	 (if *dest*
 	     (close-output-port p)))))
	;; Copyright 2010 the V8 project authors. All rights reserved.
	;; Redistribution and use in source and binary forms, with or without
	;; modification, are permitted provided that the following conditions are
	;; met:
	;;
	;; * Redistributions of source code must retain the above copyright
	;; notice, this list of conditions and the following disclaimer.
	;; * Redistributions in binary form must reproduce the above
	;; copyright notice, this list of conditions and the following
	;; disclaimer in the documentation and/or other materials provided
	;; with the distribution.
	;; * Neither the name of Google Inc. nor the names of its
	;; contributors may be used to endorse or promote products derived
	;; from this software without specific prior written permission.
	;;
	;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	;; This is a Scheme script for the Bigloo compiler. Bigloo must be compiled with
	;; support for bignums. The compilation of the script can be done as follows:
	;; bigloo -static-bigloo -o generate-ten-powers generate-ten-powers.scm
	;;
	;; Generate approximations of 10^k.

	(module gen-ten-powers
	(static (class Cached-Fast
	v::bignum
	e::bint
	exact?::bool))
	(main my-main))


	;;----------------bignum shifts -----------------------------------------------
	(define (bit-lshbx::bignum x::bignum by::bint)
	(if (<fx by 0)
	#z0
	(*bx x (exptbx #z2 (fixnum->bignum by)))))

	(define (bit-rshbx::bignum x::bignum by::bint)
	(if (<fx by 0)
	#z0
	(/bx x (exptbx #z2 (fixnum->bignum by)))))

	;;----------------the actual power generation -------------------------------

	;; e should be an indication. it might be too small.
	(define (round-n-cut n e nb-bits)
	(define max-container (- (bit-lshbx #z1 nb-bits) 1))
	(define (round n)
	(case round
	((down) n)
	((up)
	(+bx n
	;; with the -1 it will only round up if the cut off part is
	;; non-zero
	(-bx (bit-lshbx #z1
	(-fx (+fx e nb-bits) 1))
	#z1)))
	((round)
	(+bx n
	(bit-lshbx #z1
	(-fx (+fx e nb-bits) 2))))))
	(let* ((shift (-fx (+fx e nb-bits) 1))
	(cut (bit-rshbx (round n) shift))
	(exact? (=bx n (bit-lshbx cut shift))))
	(if (<=bx cut max-container)
	(values cut e exact?)
	(round-n-cut n (+fx e 1) nb-bits))))

	(define (rounded-/bx x y)
	(case round
	((down) (/bx x y))
	((up) (+bx (/bx x y) #z1))
	((round) (let ((tmp (/bx (*bx #z2 x) y)))
	(if (zerobx? (remainderbx tmp #z2))
	(/bx tmp #z2)
	(+bx (/bx tmp #z2) #z1))))))

	(define (generate-powers from to mantissa-size)
	(let* ((nb-bits mantissa-size)
	(offset (- from))
	(nb-elements (+ (- from) to 1))
	(vec (make-vector nb-elements))
	(max-container (- (bit-lshbx #z1 nb-bits) 1)))
	;; the negative ones. 10^-1, 10^-2, etc.
	;; We already know, that we can't be exact, so exact? will always be #f.
	;; Basically we will have a ten^i that we will *10 at each iteration. We
	;; want to create the matissa of 1/ten^i. However the mantissa must be
	;; normalized (start with a 1). -> we have to shift the number.
	;; We shift by multiplying with two^e. -> We encode two^e*(1/ten^i) ==
	;; two^e/ten^i.
	(let loop ((i 1)
	(ten^i #z10)
	(two^e #z1)
	(e 0))
	(unless (< (- i) from)
	(if (>bx (/bx (*bx #z2 two^e) ten^i) max-container)
	;; another shift would make the number too big. We are
	;; hence normalized now.
	(begin
	(vector-set! vec (-fx offset i)
	(instantiate::Cached-Fast
	(v (rounded-/bx two^e ten^i))
	(e (negfx e))
	(exact? #f)))
	(loop (+fx i 1) (*bx ten^i #z10) two^e e))
	(loop i ten^i (bit-lshbx two^e 1) (+fx e 1)))))
	;; the positive ones 10^0, 10^1, etc.
	;; start with 1.0. mantissa: 10...0 (1 followed by nb-bits-1 bits)
	;; -> e = -(nb-bits-1)
	;; exact? is true when the container can still hold the complete 10^i
	(let loop ((i 0)
	(n (bit-lshbx #z1 (-fx nb-bits 1)))
	(e (-fx 1 nb-bits)))
	(when (<= i to)
	(receive (cut e exact?)
	(round-n-cut n e nb-bits)
	(vector-set! vec (+fx i offset)
	(instantiate::Cached-Fast
	(v cut)
	(e e)
	(exact? exact?)))
	(loop (+fx i 1) (*bx n #z10) e))))
	vec))

	(define (print-c powers from to struct-type
	cache-name max-distance-name offset-name macro64)
	(define (display-power power k)
	(with-access::Cached-Fast power (v e exact?)
	(let ((tmp-p (open-output-string)))
	;; really hackish way of getting the digits
	(display (format "~x" v) tmp-p)
	(let ((str (close-output-port tmp-p)))
	(printf " {~a(0x~a, ~a), ~a, ~a},\n"
	macro64
	(substring str 0 8)
	(substring str 8 16)
	e
	k)))))
	(define (print-powers-reduced n)
	(print "static const " struct-type " " cache-name
	"(" n ")"
	"[] = {")
	(let loop ((i 0)
	(nb-elements 0)
	(last-e 0)
	(max-distance 0))
	(cond
	((>= i (vector-length powers))
	(print " };")
	(print "static const int " max-distance-name "(" n ") = "
	max-distance ";")
	(print "// nb elements (" n "): " nb-elements))
	(else
	(let* ((power (vector-ref powers i))
	(e (Cached-Fast-e power)))
	(display-power power (+ i from))
	(loop (+ i n)
	(+ nb-elements 1)
	e
	(cond
	((=fx i 0) max-distance)
	((> (- e last-e) max-distance) (- e last-e))
	(else max-distance))))))))
	(print "// Copyright 2010 the V8 project authors. All rights reserved.")
	(print "// ------------ GENERATED FILE ----------------")
	(print "// command used:")
	(print "// "
	(apply string-append (map (lambda (str)
	(string-append " " str))
	main-args))
	" // NOLINT")
	(print)
	(print
	"// This file is intended to be included inside another .h or .cc files\n"
	"// with the following defines set:\n"
	"// GRISU_CACHE_STRUCT: should expand to the name of a struct that will\n"
	"// hold the cached powers of ten. Each entry will hold a 64-bit\n"
	"// significand, a 16-bit signed binary exponent, and a 16-bit\n"
	"// signed decimal exponent. Each entry will be constructed as follows:\n"
	"// { significand, binary_exponent, decimal_exponent }.\n"
	"// GRISU_CACHE_NAME(i): generates the name for the different caches.\n"
	"// The parameter i will be a number in the range 1-20. A cache will\n"
	"// hold every i'th element of a full cache. GRISU_CACHE_NAME(1) will\n"
	"// thus hold all elements. The higher i the fewer elements it has.\n"
	"// Ideally the user should only reference one cache and let the\n"
	"// compiler remove the unused ones.\n"
	"// GRISU_CACHE_MAX_DISTANCE(i): generates the name for the maximum\n"
	"// binary exponent distance between all elements of a given cache.\n"
	"// GRISU_CACHE_OFFSET: is used as variable name for the decimal\n"
	"// exponent offset. It is equal to -cache[0].decimal_exponent.\n"
	"// GRISU_UINT64_C: used to construct 64-bit values in a platform\n"
	"// independent way. In order to encode 0x123456789ABCDEF0 the macro\n"
	"// will be invoked as follows: GRISU_UINT64_C(0x12345678,9ABCDEF0).\n")
	(print)
	(print-powers-reduced 1)
	(print-powers-reduced 2)
	(print-powers-reduced 3)
	(print-powers-reduced 4)
	(print-powers-reduced 5)
	(print-powers-reduced 6)
	(print-powers-reduced 7)
	(print-powers-reduced 8)
	(print-powers-reduced 9)
	(print-powers-reduced 10)
	(print-powers-reduced 11)
	(print-powers-reduced 12)
	(print-powers-reduced 13)
	(print-powers-reduced 14)
	(print-powers-reduced 15)
	(print-powers-reduced 16)
	(print-powers-reduced 17)
	(print-powers-reduced 18)
	(print-powers-reduced 19)
	(print-powers-reduced 20)
	(print "static const int GRISU_CACHE_OFFSET = " (- from) ";"))

	;;----------------main --------------------------------------------------------
	(define main-args #f)
	(define mantissa-size #f)
	(define dest #f)
	(define round #f)
	(define from #f)
	(define to #f)

	(define (my-main args)
	(set! main-args args)
	(args-parse (cdr args)
	(section "Help")
	(("?") (args-parse-usage #f))
	((("-h" "--help") (help "?, -h, --help" "This help message"))
	(args-parse-usage #f))
	(section "Misc")
	(("-o" ?file (help "The output file"))
	(set! dest file))
	(("--mantissa-size" ?size (help "Container-size in bits"))
	(set! mantissa-size (string->number size)))
	(("--round" ?direction (help "Round bignums (down, round or up)"))
	(set! round (string->symbol direction)))
	(("--from" ?from (help "start at 10^from"))
	(set! from (string->number from)))
	(("--to" ?to (help "go up to 10^to"))
	(set! to (string->number to)))
	(else
	(print "Illegal argument `" else "'. Usage:")
	(args-parse-usage #f)))
	(when (not from)
	(error "generate-ten-powers"
	"Missing from"
	#f))
	(when (not to)
	(error "generate-ten-powers"
	"Missing to"
	#f))
	(when (not mantissa-size)
	(error "generate-ten-powers"
	"Missing mantissa size"
	#f))
	(when (not (memv round '(up down round)))
	(error "generate-ten-powers"
	"Missing round-method"
	round))

	(let ((dividers (generate-powers from to mantissa-size))
	(p (if (not dest)
	(current-output-port)
	(open-output-file dest))))
	(unwind-protect
	(with-output-to-port p
	(lambda ()
	(print-c dividers from to
	"GRISU_CACHE_STRUCT" "GRISU_CACHE_NAME"
	"GRISU_CACHE_MAX_DISTANCE" "GRISU_CACHE_OFFSET"
	"GRISU_UINT64_C"
	)))
	(if dest
	(close-output-port p)))))