Hi all,
I'm implementing Google's protocol buffers in Gambit-C. One of the basic data types is a "varint" which represents a 64-bit integer as a variable number of bytes in a byte stream.
This is the first time I've tried to "decode" data from a byte stream as a signed number in Scheme. In other programming languages that don't have bignums I would have relied on integer overflow and done something like: `(+ 1 (bitwise-not value))'. Has anyone else tried to do something like this before? Is there a better way?
I fiddled around with various approaches and ended up with this:
(define (negative-64bit-value value) (copy-bit-field 63 0 value -1))
Which is used in the following way:
;; This value was accumulated by folding bytes from a stream into an ;; accumulator. The seed value was zero and each byte was added to ;; the accumulator after being aligned by ARITHMETIC-SHIFT. It is not ;; known whether the value should be positive or negative until the ;; last byte in the sequence is read from the stream. (define accumulated-value #x7fffffffffffffffffff) ;; => 604462909807314587353087
(negative-64bit-value accumulated-value) ;; => -1
Thanks,
-Ben
Afficher les réponses par date
2009/8/12 Ben Weaver ben@orangesoda.net:
I'm implementing Google's protocol buffers in Gambit-C. One of the basic data types is a "varint" which represents a 64-bit integer as a variable number of bytes in a byte stream.
Has anyone else tried to do something like this before? Is there a better way?
Well I don;t know about better, but I just convert to a plain old unsigned integer first (by the usual methods) and then, since I know the size of the physical representation I use the following code to implement the two's complement conversion (larceny-specific, but I know that Gambit has an analog for fixnum? and fxlogand):
(define max-fixnum-exponent (let find-max-fixnum ((e 16)) (if (fixnum? (expt 2 e)) (find-max-fixnum (+ e 1)) (- e 1) )))
(define (sign-bit value bit-number) (if (> bit-number max-fixnum-exponent) (sign-bit (quotient value (expt 2 max-fixnum-exponent)) (- bit-number max-fixnum-exponent)) (let ((mask (expt 2 (- bit-number 1)))) (= 0 (fxlogand value mask)) )))
(define (unsigned->signed value n-bits) (if (sign-bit value (- n-bits 1)) value (- value (expt 2 n-bits)) ))
Obviously (sign-bit ...) is the expensive part of this code, and if you were being clever and type-specific you could probably grab the sign bit on the fly as part of the conversion from a byte-stream to the unsigned integer form. HTH.
david rush