extra/rosetta-code/gray-code/gray-code.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays kernel math math.parser prettyprint ranges sequences ;
   4 IN: rosetta-code.gray-code
   5
   6 ! http://rosettacode.org/wiki/Gray_code
   7
   8 ! Gray code is a form of binary encoding where transitions
   9 ! between consecutive numbers differ by only one bit. This is a
  10 ! useful encoding for reducing hardware data hazards with values
  11 ! that change rapidly and/or connect to slower hardware as inputs.
  12 ! It is also useful for generating inputs for Karnaugh maps in
  13 ! order from left to right or top to bottom.
  14
  15 ! Create functions to encode a number to and decode a number
  16 ! from Gray code. Display the normal binary representations, Gray
  17 ! code representations, and decoded Gray code values for all 5-bit
  18 ! binary numbers (0-31 inclusive, leading 0's not necessary).
  19
  20 ! There are many possible Gray codes. The following encodes what
  21 ! is called "binary reflected Gray code."
  22
  23 ! Encoding (MSB is bit 0, b is binary, g is Gray code):
  24 !   if b[i-1] = 1
  25 !      g[i] = not b[i]
  26 !   else
  27 !      g[i] = b[i]
  28
  29 ! Or:
  30 !   g = b xor (b logically right shifted 1 time)
  31
  32 ! Decoding (MSB is bit 0, b is binary, g is Gray code):
  33 !   b[0] = g[0]
  34 !   b[i] = g[i] xor b[i-1]
  35
  36 : gray-encode ( n -- n' ) dup -1 shift bitxor ;
  37
  38 :: gray-decode ( n! -- n' )
  39     n :> p!
  40     [ n -1 shift dup n! 0 = not ] [
  41         p n bitxor p!
  42     ] while
  43     p ;
  44
  45 : gray-code-main ( -- )
  46     -1 32 [a..b] [
  47         dup [ >bin ] [ gray-encode ] bi
  48         [ >bin ] [ gray-decode ] bi 4array .
  49     ] each ;
  50
  51 MAIN: gray-code-main