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