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