Scheme - Combining hex values in a string

Author

Combining hex values in a string

netytan

2006-03-04, 9:56 pm

Hey,

This isn't exactly a Scheme question, but I am using Scheme so it
seemed like the logical place to ask for help.

So I have a string containing 4 hex numbers 98, ff, 00, and 01. What I
need to do is to combine them to produce the value 16842648, but I
can't seem to figure it out. I know how to read and construct hex
numbers in general that's not a problem, but not when the numbers have
been grouped like this. Have to say I'm a little lost.

The string I have looks like this: "\x98\xff\x00\x01"; I can easily get
the numbers from this into a list so then I have the list (152 255 0
1).

Heres what I have so far to compute this:

(map char->integer (string->list "\x98\xff\x00\x01"))

Does anyone know how to do this?

Thanks a lot,

Mark.

William Xu

2006-03-04, 9:56 pm

"netytan" <netytan@gmail.com> writes:

> So I have a string containing 4 hex numbers 98, ff, 00, and 01. What I
> need to do is to combine them to produce the value 16842648, but I
> can't seem to figure it out. I know how to read and construct hex
> numbers in general that's not a problem, but not when the numbers have
> been grouped like this. Have to say I'm a little lost.
>
> The string I have looks like this: "\x98\xff\x00\x01"; I can easily get
> the numbers from this into a list so then I have the list (152 255 0
> 1).
>
> Heres what I have so far to compute this:
>
> (map char->integer (string->list "\x98\xff\x00\x01"))
>
> Does anyone know how to do this?

I happen to just have the following. Here, `ash' will shift a number
left.

(define (binary-list->integer lst)
"Convert a binary-list LST to an integer. e.g.,
(binary-list->integer '(0 #x68))
=> #x68"
(let loop ((lst lst)
(n 0))
(if (null? lst)
n
(loop (cdr lst)
(+ (ash (car lst) (* (1- (length lst)) 8))
n)))))

So,

(binary-list->integer
(map char->integer (string->list "\x98\xff\x00\x01")))

=> 2566848513

--
William

netytan

2006-03-05, 3:57 am

Amazing, thanks William thats just what I was looking for. I'm not sure
where ash came from, it's not included as a built-in in plt scheme but
it is in petite.

(ash n p) can be defined as being n x 2 ^ p though so it can be made to
work on multiple schemes :). Assuming that ash isn't implemented as
part of SLIB.

How did you ever think of that :). That's crazy lol. Good work!

Thanks again,

Mark.

William Xu

2006-03-05, 3:57 am

"netytan" <netytan@gmail.com> writes:

> Amazing, thanks William thats just what I was looking for. I'm not sure
> where ash came from, it's not included as a built-in in plt scheme but
> it is in petite.

Hmm, i forgot to mention. I use Guile.

> (ash n p) can be defined as being n x 2 ^ p though so it can be made to
> work on multiple schemes :). Assuming that ash isn't implemented as
> part of SLIB.

Not exactly as its definition in Guile, where CNT could be negative.
Its doc explains quite well,

guile> (help ash)
`ash' is a primitive procedure in the (guile) module.

-- Scheme Procedure: ash n cnt
Return N shifted left by CNT bits, or shifted right if CNT is
negative. This is an "arithmetic" shift.

This is effectively a multiplication by 2^CNT, and when CNT is
negative it's a division, rounded towards negative infinity.
(Note that this is not the same rounding as `quotient' does.)

With N viewed as an infinite precision twos complement, `ash'
means a left shift introducing zero bits, or a right shift
dropping bits.

(number->string (ash #b1 3) 2) => "1000"
(number->string (ash #b1010 -1) 2) => "101"

;; -23 is bits ...11101001, -6 is bits ...111010
(ash -23 -2) => -6

guile>

> How did you ever think of that :). That's crazy lol. Good work!

This sort of operations seem common in C. :P

--
William

Pascal Bourguignon

2006-03-05, 3:57 am

"netytan" <netytan@gmail.com> writes:

> Hey,
>
> This isn't exactly a Scheme question, but I am using Scheme so it
> seemed like the logical place to ask for help.
>
> So I have a string containing 4 hex numbers 98, ff, 00, and 01. What I
> need to do is to combine them to produce the value 16842648, but I
> can't seem to figure it out. I know how to read and construct hex
> numbers in general that's not a problem, but not when the numbers have
> been grouped like this. Have to say I'm a little lost.
>
> The string I have looks like this: "\x98\xff\x00\x01"; I can easily get
> the numbers from this into a list so then I have the list (152 255 0
> 1).
>
> Heres what I have so far to compute this:
>
> (map char->integer (string->list "\x98\xff\x00\x01"))
>
> Does anyone know how to do this?

Don't you know how to write numbers in base ten?

1234 = ((1*ten+2)*ten+3)*ten+4

Well, it's exactly the same, only the base is two-hundred-and-fifty-six.
Let's call it base:

1234 = ((1*base+2)*base+3)*base+4
99,ff,00,01 = ((99*base+ff)*base+00)*base+01

Where's the difficulty?

(define (digits->integer digits base)
(cond ((null? digits) 0)
((null? (cdr digits)) (car digits))
(else (+ (car digits) (* base (digits->integer (cdr digits) base))))))

(digits->integer (reverse '(1 2 3 4)) 10) --> 1234
(digits->integer (reverse '(#x99 #xff #x00 #x01)) 256) --> 2583625729
(digits->integer (reverse '(#x01 #x00 #xff #x99)) 256) --> 16842649

Your digits are probably in the wrong order (little-endian).

(define (remove item list)
(cond ((null? list) list)
((eqv? item (car list)) (remove item (cdr list)))
(else (cons (car list) (remove item (cdr list))))))

(define (position item string)
(let loop ((i 0))
(cond ((>= i (length string)) #f)
((eqv? item (string-ref string i)) i)
(else (loop (+ 1 i))))))

(define (hex->integer char)
(or (position char "0123456789abcdef")
(position char "0123456789ABCDEF")))

(map hex->integer (remove #\\ (remove #\x (string->list buffer))))
--> (9 9 15 15 0 0 0 1)

Since the bytes are in the wrong order (little-endian), but the nibble
are in the right order (big-endian), we must either
convert first the bytes, next the number:

(define (convert-stuff buffer)
(digits->integer
(let loop ((digits (map hex->integer
(remove #\\ (remove #\x (string->list buffer)))))
(bytes '()))
(if (or (null? digits) (null? (cdr digits)))
(reverse bytes)
(loop (cddr digits)
(cons (digits->integer (list (cadr digits) (car digits)) 16)
bytes))))
256))

(convert-stuff "\\x99\\xff\\x00\\x01") --> 16842649

or swap the nibbles:

(define (swap-nibbles list)
(cond ((or (null? list) (null? (cdr list))) '())
(else (cons (cadr list) (cons (car list) (swap-nibbles (cddr list)))))))

(define (convert-stuff buffer)
(digits->integer
(swap-nibbles (map hex->integer
(remove #\\ (remove #\x (string->list buffer)))))
16))

(convert-stuff "\\x99\\xff\\x00\\x01") --> 16842649

but this is not what you wanted...

Note, the parsing is rather dumb, but you didn't specify the syntax of
your input buffer! Perhaps "\\x1\\x23" is valid and means (hex)2301?
But we parse it as (hex)12.

--
__Pascal Bourguignon__ http://www.informatimago.com/

WARNING: This product warps space and time in its vicinity.

Jens Axel Søgaard

2006-03-05, 3:57 am

netytan wrote:
> Amazing, thanks William thats just what I was looking for. I'm not sure
> where ash came from, it's not included as a built-in in plt scheme but
> it is in petite.
>
> (ash n p) can be defined as being n x 2 ^ p though so it can be made to
> work on multiple schemes :). Assuming that ash isn't implemented as
> part of SLIB.

A search for either "arithmetic" or "shift" in the HelpDesk will
lead you to:

(arithmetic-shift n m) returns the bitwise ``shift'' of n. The integer
n is shifted left by m bits; i.e., m new zeros are introduced as
rightmost digits. If m is negative, n is shifted right by - m bits;
i.e., the rightmost m digits are dropped.

--
Jens Axel Søgaard

netytan

2006-03-05, 9:57 pm

Pascal Bourguignon wrote:
> "netytan" <netytan@gmail.com> writes:
>
>
> Don't you know how to write numbers in base ten?
>
> 1234 = ((1*ten+2)*ten+3)*ten+4
>
> Well, it's exactly the same, only the base is two-hundred-and-fifty-six.
> Let's call it base:
>
> 1234 = ((1*base+2)*base+3)*base+4
> 99,ff,00,01 = ((99*base+ff)*base+00)*base+01
>
> Where's the difficulty?
>
> (define (digits->integer digits base)
> (cond ((null? digits) 0)
> ((null? (cdr digits)) (car digits))
> (else (+ (car digits) (* base (digits->integer (cdr digits) base))))))
>
>
> (digits->integer (reverse '(1 2 3 4)) 10) --> 1234
> (digits->integer (reverse '(#x99 #xff #x00 #x01)) 256) --> 2583625729
> (digits->integer (reverse '(#x01 #x00 #xff #x99)) 256) --> 16842649
>
> Your digits are probably in the wrong order (little-endian).
>
>
> (define (remove item list)
> (cond ((null? list) list)
> ((eqv? item (car list)) (remove item (cdr list)))
> (else (cons (car list) (remove item (cdr list))))))
>
> (define (position item string)
> (let loop ((i 0))
> (cond ((>= i (length string)) #f)
> ((eqv? item (string-ref string i)) i)
> (else (loop (+ 1 i))))))
>
> (define (hex->integer char)
> (or (position char "0123456789abcdef")
> (position char "0123456789ABCDEF")))
>
>
> (map hex->integer (remove #\\ (remove #\x (string->list buffer))))
> --> (9 9 15 15 0 0 0 1)
>
> Since the bytes are in the wrong order (little-endian), but the nibble
> are in the right order (big-endian), we must either
> convert first the bytes, next the number:
>
> (define (convert-stuff buffer)
> (digits->integer
> (let loop ((digits (map hex->integer
> (remove #\\ (remove #\x (string->list buffer)))))
> (bytes '()))
> (if (or (null? digits) (null? (cdr digits)))
> (reverse bytes)
> (loop (cddr digits)
> (cons (digits->integer (list (cadr digits) (car digits)) 16)
> bytes))))
> 256))
>
> (convert-stuff "\\x99\\xff\\x00\\x01") --> 16842649
>
>
> or swap the nibbles:
>
> (define (swap-nibbles list)
> (cond ((or (null? list) (null? (cdr list))) '())
> (else (cons (cadr list) (cons (car list) (swap-nibbles (cddr list)))))))
>
> (define (convert-stuff buffer)
> (digits->integer
> (swap-nibbles (map hex->integer
> (remove #\\ (remove #\x (string->list buffer)))))
> 16))
>
> (convert-stuff "\\x99\\xff\\x00\\x01") --> 16842649
>
> but this is not what you wanted...
>

3 cheers for Pascal he's cracked it perfectly and produced the number I
was given originally :D. Let me explain:

I was working with a friend to convert unpack from Python so he could
use it in Scheme. He gave me the hex string and the number - when
William posted his code and I saw that I'd already come across the
value he posted while trying in vain to get to "right" number. I tested
unpack in Python and the numbers matched.

Thats two sides of the coin resolved.

Pascal: If you use \\x98 at the beginning of your examples then you
should get the value you were looking for, it's just a little typo I
think. The problem was that the hex is being read from a binary file so
we don't have the the value as a string that can be parse, but it can
be converted to a list of numbers.

Your first examples solved the problem anyway; with a minor change to
the code I think it would be clearer.

Far be it for me to correct you but you can remove the middle condition
of your digits->integer function and get the same results. Once this is
done you can replace the cond with an if and your code looks like this:

(define (digits->integer digits base)
(if (null? digits)
0
(+ (car digits) (* base (digits->integer (cdr digits) base)))))

I should have been more clear when I posted the Q, I will in the future
:).

Oh, and yes I can count in base 10 though I haven't seen it put out
like that before :). Rest assured that it's now in my little blue
notebook and will be remembered.

I'm a first year student and everything I've learned in the last 4-5
years has been from myself while traveling, this didn't include maths
at all until last year when playing with assembly and nothing formal
before this year :).

I have plenty left to learn and I'm enjoying learning it, I really
appreciate your help Pascal :).

Thanks for all your wonderful help everyone,

Mark.

Pascal Bourguignon

2006-03-05, 9:57 pm

"netytan" <netytan@gmail.com> writes:

> Far be it for me to correct you but you can remove the middle condition
> of your digits->integer function and get the same results. Once this is
> done you can replace the cond with an if and your code looks like this:
>
> (define (digits->integer digits base)
> (if (null? digits)
> 0
> (+ (car digits) (* base (digits->integer (cdr digits) base)))))

Right.

> I should have been more clear when I posted the Q, I will in the future
> :).
>
> Oh, and yes I can count in base 10 though I haven't seen it put out
> like that before :). Rest assured that it's now in my little blue
> notebook and will be remembered.

Yes. The point is that it's a mere base conversion. The same
algorithm applies whatever the base.

> I'm a first year student and everything I've learned in the last 4-5
> years has been from myself while traveling, this didn't include maths
> at all until last year when playing with assembly and nothing formal
> before this year :).
>
> I have plenty left to learn and I'm enjoying learning it, I really
> appreciate your help Pascal :).
>
> Thanks for all your wonderful help everyone,
>
> Mark.
>

--
__Pascal Bourguignon__ http://www.informatimago.com/

Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.

Sponsored Links