Binary Coding To Gray Coding and viceversa

[Psychophanta]

Another almost useless code. But who knows, may be you will need it someday

Code: Select all

;Albert (Psychophanta) February 2008:
Procedure.l BinaryCodingToGrayCoding(n.l)
  ProcedureReturn n!(n>>1)
EndProcedure
Procedure.l GrayCodingToBinaryCoding(n.l)
  Protected t.l=Int(Log(n)/Log(2))
  Repeat
    n!(Int(Pow(2,t))&n>>1):t-1
  Until t<0
  ProcedureReturn n
EndProcedure
;Test it:
For t.l=1 To 1000
  a.l=Random(3000000)
  If a<>BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
    Debug "wrong!"
  EndIf
Next

Improvements on GrayCodingToBinaryCoding() would be welcome

EDIT 20070219:
In assembler only for longs, not quads supported:

Code: Select all

;Albert (Psychophanta) February 2008:
Procedure.l BinaryCodingToGrayCodingASM(n.l)
  !mov eax,dword[p.v_n]
  !mov ebx,eax
  !shr ebx,1
  !xor eax,ebx
  ProcedureReturn
EndProcedure
Procedure.l GrayCodingToBinaryCodingASM(n.l)
  !mov cl,1
  !mov eax,dword[p.v_n]
  !@@:mov ebx,eax
  !shr ebx,cl
  !xor eax,ebx
  !shl cl,1
  !cmp ebx,2
  !jc @f
  !cmp cl,32; <- 64 if quads (.q) instead of longs (.l)
  !jnz @r
  !@@:
  ProcedureReturn
EndProcedure
;Test it:
For t.l=1 To 10000
  a.l=Random(3000000)
  b.l=BinaryCodingToGrayCodingASM(GrayCodingToBinaryCodingASM(a))
  If a<>b
    Debug "wrong!"
  EndIf
Next

Thanks to Demivec and Pupil for their contributions.

Ah! btw, if anyone (for any strange reason) wants a quad ASM standard i386 version (much faster & better than the one from Demivec because this one allows values from 0 to 2^64-1), ask for it

[srod]

Interesting one.

When I sat down and constructed the inverse operation, I basically came up with an equivalent method to your GrayCodingToBinaryCoding() algorithm. Absolutely identical.

I'm interested to see if there is a quicker way.

[Rook Zimbabwe]

So what does it do? What is it used for?

[dell_jockey]

So what does it do? What is it used for?

Nowadays graycodes are predominantly used in signal processing. One such application that I know of is encoding altitude information onto a signal that aircraft transponders return to interrogating radar stations. For more information on this application, see: http://www.airsport-corp.com/modec.htm

[Demivec]

Improvements on GrayCodingToBinaryCoding() would be welcome

Use this for GrayCodingToBinaryCoding(), it's a gazillion times faster :

Code: Select all

;Albert (Psychophanta) February 2008:
;with GrayCodingToBinaryCoding() by Demivec

Procedure.q BinaryCodingToGrayCoding(n.q) ;largest integer that is handled is 9223372035781775807
  ProcedureReturn n ! (n >> 1)
EndProcedure

Procedure.q GrayCodingToBinaryCoding(n.q) ;largest integer that is handled is 9223372035781775807
  Protected s.q = 1,d.q
  Repeat
    d = n >> s
    n ! d
    If d < 2  Or s = 4611686018427387904
      ProcedureReturn n
    EndIf 
    s << 1
  ForEver
EndProcedure

;Test it:
For T.l = 1 To 1000
  a.q = 9223372035780000000 + Random(1775807)
  b.q = BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
  If a <> b
    Debug "wrong!"
    Break
  EndIf
Next

I also updated the code for quad sized conversions. If you only need longs, the Coding functions will work fine as they are for that also (in other words use GrayCodingToBinaryCoding(c.l) and everything is kosher too).

[Psychophanta]

Nice Demivec, your method does not make use of arithmetical functions like Log(), etc., but only logical ones, so then your way is more elegant in my opinion, but i don't know if it wins in speed too.

@Rook, you can also look at wikipedia:
http://en.wikipedia.org/wiki/Gray_code

[Rook Zimbabwe]

So that is what it was doing. I know we utilized GC in the Army, but I had no real idea about the math!

Oh well... that was for the @55h0leZ (Officers) to deal with!

[Psychophanta]

Damn!
I am stopped!
Why the hell this doesn't work? (it is a question for Coding questions section perhaps).

Code: Select all

Procedure.l BinaryCodingToGrayCoding(n.l)
  ProcedureReturn n ! (n >> 1)
EndProcedure

Procedure.l GrayCodingToBinaryCoding(n.l)
  Protected s.l = 1,d.l
  Repeat
    d = n >> s
    n ! d
    s << 1
  Until d<2 Or s=$80000000
  ProcedureReturn n
EndProcedure

;Test it:
a.l=500000;Random(1775807)
b.l=BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
If a<>b
  Debug "wrong!"
EndIf

[Pupil]

Damn!
I am stopped!
Why the hell this doesn't work? (it is a question for Coding questions section perhaps).

My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.

[Psychophanta]

My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.

Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's method is not correct, and it works casually lucky just due, in part, to the current lacks in quads.

[Pupil]

My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.

Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's code is not correct, and it works casually lucky just due to the current lacks in quads.

The expression:

Code: Select all

n ! d

will result in all kinds of numbers and the sign bit will be set in the first iteration regardless which positive number you start with. Due to this your version will give the wrong result.

[Psychophanta]

The expression:
Code:

n ! d


will result in all kinds of numbers and the sign bit will be set in the first iteration regardless which positive number you start with.

Please take a closer look because that can never happen, i.e. more significative bit will never be '1' in that example.
Moreover, you can try: if you replace it by

Code: Select all

n = (n ! d) & $7fffffff

it continues not working, so that not seem to be the reason
If change

Code: Select all

GrayCodingToBinaryCoding(n.l) 

by

Code: Select all

GrayCodingToBinaryCoding(n.q) 

it works, and the for the same reason the Demivec version works.

[Pupil]

Yes, you're quite right, my misstake. If the signbit isn't set from the begining there shouldn't be any problem like i described.

Instead it seems to be some special condition that occurs when s=32. The asm shift instruction masks the shift length to 5 bits so it interprets the case when s=32 to this "d = n >> 0", this is what causes the faulty result. Change the code to this and se if it works as expected?

Code: Select all

Procedure.l GrayCodingToBinaryCoding(n.l)
  Protected s.l = 1,d.l
  Repeat
    d = n >> s ;& ($7fffffff >> (s-1))
    n ! d
    s << 1
  Until d<2 Or s=32
  ProcedureReturn n
EndProcedure

[Psychophanta]

...it interprets the case when s=32 to this "d = n >> 0", this is what causes the faulty result.

Exactly, it is certainly what there is happening. My last code (which is the same as Demivec algorithm) doesn't work because a bug with >> in longs when the right parameter is 32.
I have discovered it with this code watching the local variables:

Code: Select all

Procedure.l BinaryCodingToGrayCoding(n.l)
  ProcedureReturn n ! (n >> 1)
EndProcedure

Procedure.l GrayCodingToBinaryCoding(n.l,nn.q)
  Protected s.l = 1,d.l ,dd.q
  Repeat
    d = n >> s :dd = nn >> s
    n ! d:nn!dd
    s << 1
  Until d<2 And dd<2; Or s=$80000000
  ProcedureReturn nn
EndProcedure

;Test it:
a.l=500000;Random(1775807)
CallDebugger
b.l=BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a,a))
If a<>b
  Debug "wrong!"
EndIf

My apologies to Demivec when i said his code was not correct, but @Demivec, your code is very very advanced... ... Where did you copied from

[Demivec]

My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.

Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's method is not correct, and it works casually lucky just due, in part, to the current lacks in quads.

@Psychophanta: appology accepted.
My code was been tested with integer values from 0 to 9223372035781775807 before I first posted.

The lack in quads only affects the code I posted because it affects the IF-Endif comparison. That comparison doesn't allow a function that returns a quad to be used in a comparison. I work around this by assigning the function's return value to a variable, then use the variable in the comparison. Quads also can't be returned from Random().

If you want to limit the use of quads you have 2 choices. One, you can just use a long for the input to the function and store the return in a long (this will limit the range of integers to 0 - 2147483646). Two if you change the functions to use only long variables, parameters and returns (this will limit the range of integers to 0 - 131071). If you take the second choice it will dumb the procedure down to the version you are currently trying to debug (hint: it only accepts #'s upto 131071). I went through all these options before I posted the code above. Take your pick.

Your original code could not be used on values equal to zero. It caused a wrap to occur and you had to wait for the value to count down from 2147483647 to 0 before it exited. Try it and see, I used this statement for the time test: GrayCodingToBinaryCoding(0). That's how I came to the precise speed increase of a gazillion times.

One more comment, the "Until d<2 or s=something" is used to determine when shifting any more would be useless. Either it has run out of bits to shift (d<2 which affects shifts to the right) or it has run into a maximum value (s=something, which affects shifts to the left). The shift to the left value is equal to the size of the variable with all bits on except the sign bit (or high bit). For example in my code it equals $4000000000000000.