home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 700s / rfc798.txt < prev    next >
Text File  |  1992-10-14  |  39KB  |  987 lines

  1.  
  2.  
  3. Network Working Group                                            A. Katz
  4. Request for Comments: 798                                            ISI
  5.                                                           September 1981
  6.  
  7.  
  8.               DECODING FACSIMILE DATA FROM THE RAPICOM 450
  9.  
  10. I.   Introduction
  11.  
  12.    This note  describes  the  implementation  of  a  program  to  decode
  13.    facsimile  data from the Rapicom  450 facsimile (fax) machine into an
  14.    ordinary  bitmap.  This bitmap can then be displayed on other devices
  15.    or edited  and then encoded  back into the Rapicom  450  format.   In
  16.    order  to do this,  it  was  necessary  to  understand  the  how  the
  17.    encoding/decoding  process  works  within  the  fax  machine  and  to
  18.    duplicate  that process  in a program.  This algorithm is descibed in
  19.    an article  by Weber  [1] as well as in a memo by Mills [2], however,
  20.    more information  than is presented  in these papers  is necessary to
  21.    successfully decode the data.
  22.  
  23.    The program  was written  in L10 as a subsystem  of  NLS  running  on
  24.    TOPS20.   The fax machine  is interfaced  to  TOPS20  as  a  terminal
  25.    through a microprocessor-based interface called FAXIE.
  26.  
  27.    Grateful  acknowledgment  is made to Steve  Treadwell  of  University
  28.    College,  London and Jon Postel of Information Sciences Institute for
  29.    their assistance.
  30.  
  31. II.  Interface to TOPS20
  32.  
  33.    The fax machine  is connected  to a microprocessor-based  unit called
  34.    FAXIE,  designed  and built by Steve Casner  and  Bob  Parker.   More
  35.    detailed  information  can be  found  in  reference  [3].   FAXIE  is
  36.    connected  to TOPS20  over a terminal line, and a program was written
  37.    to read  data  over  this  line and store it in a file.  The decoding
  38.    program reads the fax data from this file.
  39.  
  40.    The data comes from the fax machine  serially.  FAXIE reads this data
  41.    into an 8-bit shift register  and sends the 8-bit byte  (octet)  over
  42.    the terminal line.  Since the fax machine assigns MARK to logical 0's
  43.    and SPACE to logical  1's  (which  is  backward  from  RS232),  FAXIE
  44.    complements  each bit in the octet.   The data is sent to  TOPS20  in
  45.    octets,  the most significant bit first.  If you read each octet from
  46.    most significant  bit to least significant  bit in  the  order  FAXIE
  47.    sends  the data to TOPS20,  you would be reading the data in the same
  48.    order in comes into FAXIE from the fax machine.
  49.  
  50.    The standard  for storing  Rapicom 450 Facsimile Data is described in
  51.    RFC 769 [4].   According  to this standard,  each octet  coming  from
  52.    FAXIE must be complemented and inverted (i.e. invert the order of the
  53.    bits in the octet).   Thus,  the receiving  program  did this  before
  54.  
  55.  
  56.  
  57. Alan R. Katz                                                    [page 1]
  58.  
  59.  
  60.                                                                         
  61. DECODING FACSIMILE DATA                                          RFC 798
  62. II. Interface to TOPS20                                                 
  63.  
  64.  
  65.  
  66.    storing  the data in a file.   When the decoding  program  reads this
  67.    file,  it must invert  and complement  each octet before  reading the
  68.    data.
  69.  
  70.    Each data block  from the fax machine  is 585 bits long.   The end of
  71.    this  data  is padded  with  7 0's to make  592 bits  or  74  octets.
  72.    According  to RFC 769,  this data is stored  in a file preceded  by a
  73.    length octet and a command octet.  The possible commands are:
  74.  
  75.       56 (70 octal)--This  is a Set-Up  block  (the first  block  of the
  76.       file, contains information about the fax image)
  77.  
  78.       57 (71 octal)--This is a data block (the rest of the blocks in the
  79.       file except for the last one)
  80.  
  81.       58 (72 octal)--End command (the last block of the file)
  82.  
  83.    The length field tells how many octets in this block and is always 76
  84.    (114 octal) except for the END command which can be 2 (no data).  The
  85.    length and command octets are NOT inverted and complemented.
  86.  
  87.    Below is a diagram of each block in the file:
  88.  
  89.       +--------+--------+--------+--------+--------+--------+--------
  90.       | length | command|  data  |  data  |  ...   |        |
  91.       +--------+--------+--------+--------+--------+--------+--------
  92.  
  93. III. The Rapicom 450 Encoding Algorithm
  94.  
  95.    An ordinary  8 1/2"  by 11"  document  is made  up of about 2100 scan
  96.    lines,  each line has 1726 pels (picture  elements)  in it.  Each pel
  97.    can be either black (1) or white (0).
  98.  
  99.    The Rapicom  450 has three picture  quality  modes.   In fine  detail
  100.    mode,  all of the document  is encoded.   In quality  mode only every
  101.    other  scan line is encoded  and it is intended  that  these  missing
  102.    lines are filled  in on playback  by replicating  the previous  line.
  103.    There is also express mode, where only every third line is encoded.
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115. [page 2]                                                    Alan R. Katz
  116.  
  117.  
  118.  
  119. RFC 798                                          DECODING FACSIMILE DATA
  120.                                  III. The Rapicom 450 Encoding Algorithm
  121.  
  122.  
  123.  
  124.    Data is encoded  two lines at a time, using a special two dimensional
  125.    run-length encoding scheme.  There are 1726 pels on top and 1726 pels
  126.    on the bottom.   Each pair (top-bottom)  of pels is called  a column.
  127.    For  each  of  the  1726  columns  you  can  have  any  one  of  four
  128.    configurations (called states):
  129.  
  130.               column
  131.            (top-bottom)        pels         state
  132.            ------------        ----         ------
  133.                W-W             0,0            0
  134.                W-B             0,1            1
  135.                B-W             1,0            2
  136.                B-B             1,1            3
  137.  
  138.    The  encoding   algorithm   can  be   described   in   terms   of   a
  139.    non-deterministic finite-state automaton shown in Fig. 1 (after Mills
  140.    [2]).   You start out in a state (0-3) and transform to another state
  141.    by emitting  the appropriate  bits  marked  along  the  arcs  of  the
  142.    diagram.   For example,  suppose  you are in state  1 (WB).  To go to
  143.    state  2 (BW), you would output the bits 101 (binary); to go to state
  144.    0 (WW)  you would output the bits 1000.  Note that the number of bits
  145.    on each transition is variable.
  146.  
  147.    In states  0 (WW) and 3 (BB), a special run length encoding scheme is
  148.    used.   There are two state variables  associated  with each of these
  149.    states.   One variable  is a run-length  counter and the other is the
  150.    field  length  (in bits)  of this counter.   Upon entry  to either of
  151.    these  two  states,  the  counter  is  initialized  to  zero  and  is
  152.    incremented  for every additional  column  of the same state.  At the
  153.    end of the run,  this counter  is transmitted,  extending  with  high
  154.    order  zeros  if necessary.   If the count  fills up the field, it is
  155.    transmitted,  the field length  is incremented  by one, and the count
  156.    starts  again.   This count  is called  the run length word and it is
  157.    between 2 and 7 bits long.
  158.  
  159.    For example,  suppose  we are in state  0 (WW) and the run length for
  160.    this state  (refered to as the white run length) is 3.  Suppose there
  161.    are three 0's in a row.  The first 0 was encoded when we came to this
  162.    state,  there  are two more 0's that must be encoded.   Thus we would
  163.    send a 010 (binary).   Similarly, if there are seven 0's in a row, we
  164.    would send a 110, but eight 0's would be sent by 111 followed by 0000
  165.    and the white run length becomes 4.  (Ten 0's would be encoded as 111
  166.    followed by 0010 and the white run length would be 4).
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173. Alan R. Katz                                                    [page 3]
  174.  
  175.  
  176.                                                                         
  177. DECODING FACSIMILE DATA                                          RFC 798
  178. III. The Rapicom 450 Encoding Algorithm                                 
  179.  
  180.  
  181.  
  182.    
  183.                                   0100
  184.             ------------------------>-----------------------------------
  185.             |                                                          |
  186.             |    -------------------<-------------------------------   |
  187.             |   |                  1                               |   |
  188.             |   V                                                  |   |
  189.       ----------------                       -----------------     |   |
  190.       |              |                       |               |     |   |
  191.       |              |          010          |               |     |   |
  192.    |->|      2       |---------------------->|       1       |->|  |   |
  193.    |  |              |                       |               |  |  |   |
  194.   0|  |     B-W      |          101          |      W-B      |  |1 |   |
  195.    |<-|              |<----------------------|               |<-|  |   |
  196.       |              |                       |               |     |   |
  197.       |              |                 ----->|               |     |   |
  198.       ----------------                 |     -----------------     |   |
  199.           |   ^                        |      |     |   ^          |   |
  200.           |   |     ------------>------|      |     |   |          |   |
  201.           |   |     |           1             |     |   |          |   |
  202.           |   |     |                         |     |   |          ^   V
  203.           |   |     |                         |     |   |          |   |
  204.       0111|   |1    |                         | 1000|   |1         |   |
  205.           |   |     |                         |     |   |          |   |
  206.           |   |     |                         |     |   |          |   |
  207.           |   |     |                         |     |   |          |   |
  208.           |   |     |            1011         |     |   |          |   |
  209.           |   |     |    ----------<-----------     |   |          |   |
  210.           V   |     |    |                          V   |          |   |
  211.       ----------------   |                   -----------------     |   |
  212.       |              |<---                   |               |     |   |
  213.       |              |          0            |               |     |   |
  214.       |      3       |<----------------------|       0       |------   |
  215.       |              |                       |               |         |
  216.       |     B-B      |                       |      W-W      |         |
  217.       |              |---------------------->|               |<---------
  218.       |              |          0            |               |
  219.       |              |                       |               |
  220.       ----------------                       -----------------
  221.           |    ^                                   |    ^
  222.           |    |                                   |    |
  223.           ------                                   ------
  224.            run                                      run
  225.                                Figure 1.
  226.      Non-deterministic finite-state machine diagram for RAPICOM 450
  227.  
  228.  
  229.  
  230.  
  231. [page 4]                                                    Alan R. Katz
  232.  
  233.  
  234.  
  235. RFC 798                                          DECODING FACSIMILE DATA
  236.                                  III. The Rapicom 450 Encoding Algorithm
  237.  
  238.  
  239.  
  240.    Run length word lengths must be between 2 and 7.  The field length is
  241.    decremented if the run is encoded in one word and:
  242.  
  243.       1.  If the run length is 3 and the highest order bit is 0.
  244.  
  245.       2.  Or, if the run length is 4, 5, 6, or 7 and the highest order 2
  246.       bits are 0.
  247.  
  248.    In addition to all this, there is a special rule to follow if the run
  249.    occupies at least two run words (and can involve incrementing the run
  250.    word  size)  and the run ends  exactly at the end of a scan line.  In
  251.    this case, the last word of the run is tested for decrement as if the
  252.    previous words in the run did not exist.
  253.  
  254.    An Example:
  255.  
  256.       To confirm  the reader's  understanding of the encoding procedure,
  257.       suppose  we had the following  portion  of  a  document  (1=black,
  258.       0=white):
  259.  
  260.          top row:      0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 ...
  261.          bottom row:   1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 ...
  262.          -----------   -------------------------------
  263.          state:        1 3 3 3 3 2 0 0 0 0 0 2 2 1 0 0 ...
  264.  
  265.       Suppose  also that the black  run field length is 2, the white run
  266.       length  is 3,  and the state  is  1.   (This  example  comes  from
  267.       reference [1].)
  268.  
  269.       This portion would be encoded as:
  270.  
  271.          1 1011 11 000 1 0100 100 1 0 010 1000 ...
  272.  
  273.       NOTE:  It turns out that the Rapicom 450 sends the bits of a field
  274.       in reverse  order.   This will be  discussed  in  the  section  V.
  275.       However,  since each run length  field is sent reversed, the above
  276.       encoded bit pattern would actually be sent as:
  277.  
  278.          1 1011 11 000 1 0100 001 1 0 010 1000 ...
  279.                                ^
  280.                                |-this is actually 100 reversed
  281.  
  282.  
  283.  
  284.  
  285.  
  286.  
  287.  
  288.  
  289. Alan R. Katz                                                    [page 5]
  290.  
  291.  
  292.                                                                         
  293. DECODING FACSIMILE DATA                                          RFC 798
  294. III. The Rapicom 450 Encoding Algorithm                                 
  295.  
  296.  
  297.  
  298.    Another Example:
  299.  
  300.       This example  illustrates the rule for decrementing the run length
  301.       word lengths:
  302.  
  303.          top row:      0 1 1 0 0 1 1 1 1 1 0 0 ...
  304.          bottom row:   1 1 1 1 1 0 1 1 1 1 1 0 ...
  305.          -----------   -----------------------
  306.          state:        1 3 3 1 1 2 3 3 3 3 1 0 ...
  307.  
  308.       Here, let us suppose that the black run field length is now 4, the
  309.       white is still 3, and the state is 1.
  310.  
  311.       This portion would be encoded as:
  312.  
  313.          1 1011 0001 1 1 101 0111 011 1 1000 ...
  314.                   ^                ^
  315.                   |-goes to 3      |-blk cnt goes to 2
  316.  
  317.       When we reverse  the order of the run fields, the bit pattern that
  318.       is actually sent is:
  319.  
  320.          1 1011 1000 1 1 101 0111 110 1 1000 ...
  321.                  ^
  322.                  |-this is actually 0001 reversed, etc.
  323.  
  324. IV.  The Setup Block and the Data Header
  325.  
  326.    Each data block from the fax machine is 585 bits long.  The number of
  327.    blocks  in a  picture  is  variable  and  depends  on  the  size  and
  328.    characteristics of the picture.  It should be emphasized that a block
  329.    can end in the middle  of a scan  line of the document.  There can in
  330.    fact be many scan lines in a block.
  331.  
  332.    The 585 bit data  block  is composed  of a 24 bit sync  code which is
  333.    used to recognize the beginning of a block, a 37 bit header, 512 bits
  334.    of actual data, and a 12 bit CRC checksum:
  335.  
  336.       ------------------------------------------------------------------
  337.       |  24-bit  |    37-bit   |         512-bit         |    12-bit   |
  338.       |sync code |    header   |           data          |   checksum  |
  339.       ------------------------------------------------------------------
  340.  
  341.    The number  of useful  data bits is variable and can be between 0 and
  342.    512 (although there are always 512 bits there, some of them are to be
  343.    ignored).  The number of data bits to be used is given in the header.
  344.  
  345.  
  346.  
  347. [page 6]                                                    Alan R. Katz
  348.  
  349.  
  350.  
  351. RFC 798                                          DECODING FACSIMILE DATA
  352.                                  IV. The Setup Block and the Data Header
  353.  
  354.  
  355.  
  356.    The 37 bits of header is composed of:
  357.  
  358.       ------------------------------------------------------------------
  359.       | 2-bit |5-bit|  10-bit  |   12-bit  |  3-bit   |   3-bit  |2-bit|
  360.       |seq num|flags|data count| x position|black size|white size|state|
  361.       ------------------------------------------------------------------
  362.  
  363.    An explanation of these fields follows:
  364.  
  365.       IMPORTANT  NOTE:   Most (but not all)  of these fields are sent by
  366.       the fax machine  in REVERSE  ORDER.  The order of each n-bit field
  367.       must be inverted.
  368.  
  369.       Sync code
  370.  
  371.          This is used to synchronize  on each block.   The value of this
  372.          24 bit field is 30474730 octal (not reversed).
  373.  
  374.       Sequence number
  375.  
  376.          This number  cycles through 0, 1, 2, 3 for the data blocks.  It
  377.          is 0 for the Set-Up block (not reversed).
  378.  
  379.       Flags
  380.  
  381.          Each of these flags are 1 bit wide:
  382.  
  383.             Run
  384.  
  385.                Purpose unknown, it always seems to be 1.
  386.  
  387.             Cofb
  388.  
  389.                Purpose unknown, it always seems to be 0.
  390.  
  391.             Rpt
  392.  
  393.                1 for Set-Up  blocks (which are repeated when coming from
  394.                the fax machine  though only one of them is transfered by
  395.                FAXIE  to TOPS20  and stored  in the file) and 0 for data
  396.                blocks.
  397.  
  398.             Spare
  399.  
  400.                Purpose unknown, doesn't matter.
  401.  
  402.  
  403.  
  404.  
  405. Alan R. Katz                                                    [page 7]
  406.  
  407.  
  408.                                                                         
  409. DECODING FACSIMILE DATA                                          RFC 798
  410. IV. The Setup Block and the Data Header                                 
  411.  
  412.  
  413.  
  414.             Sub
  415.  
  416.                1 if this is a Set-Up block.
  417.  
  418.       Data Count
  419.  
  420.          Number of useful bits to use out of the 512 data bits.  NOT ALL
  421.          of the 512 data bits are used,  only this number of them.  This
  422.          number can be 0 (usually in one of the first data blocks) which
  423.          means to throw away this block. (This field is reversed!)
  424.  
  425.       X Position
  426.  
  427.          Current  position on the scan line, a value between 0 and 1725.
  428.          If this number  is greater  than where the previous  block left
  429.          off,  the intervening  space should be filled with white (0's).
  430.          If this number  is less than where the previous block left off,
  431.          set the X position  to this value  and replace  the  overlapped
  432.          data with the new data from this  block.   If  this  number  is
  433.          greater  than 1726,  ignore  this field and continue from where
  434.          the previous block left off. (This field is reversed!)
  435.  
  436.       Black Size
  437.  
  438.          The size of the black  run length  field, must be between 2 and
  439.          7.   This is the correct  value  for the black  size.   It  may
  440.          differ  from what was found  at the end of the previous  block.
  441.          (This field is reversed!)
  442.  
  443.       White Size
  444.  
  445.          The size of the white  run length  field, must be between 2 and
  446.          7.   It may differ  from  what  was found  at the  end  of  the
  447.          previous block. (This field is reversed!)
  448.  
  449.       State
  450.  
  451.          The current  state.   This is the correct state.  It may differ
  452.          from the state at the end of the previous block. (This field is
  453.          not reversed.)
  454.  
  455.       Data
  456.  
  457.          512 bits of the actual  encoding  of the document.   NOT ALL of
  458.          this data is used in general,  only the amount specified by the
  459.  
  460.  
  461.  
  462.  
  463. [page 8]                                                    Alan R. Katz
  464.  
  465.  
  466.  
  467. RFC 798                                          DECODING FACSIMILE DATA
  468.                                  IV. The Setup Block and the Data Header
  469.  
  470.  
  471.  
  472.          data count.   If this is a set  up  block,  the  data  contains
  473.          information about the type of document (see below).
  474.  
  475.       Checksum
  476.  
  477.          CRC  checksum   on   the   entire   block.    Uses   polynomial
  478.          x**12+x**8+x**7+x**5+x**3+1.
  479.  
  480.    In a setup block, the data portion of the data block consists of:
  481.  
  482.       -----------------------------------------------------------
  483.       |   6-bit |    5-bit  |   1-bit  |  20-bits  |  480-bits
  484.       |   flags |    spare  |multi page|  of zeros |  1's and 0's
  485.       -----------------------------------------------------------
  486.  
  487.    Specifically these are:
  488.  
  489.       6 flags (each are 1 bit):
  490.  
  491.          Start bit
  492.  
  493.             Always 0.
  494.  
  495.          Speed
  496.  
  497.             Is 1 if express mode.
  498.  
  499.          Detail
  500.  
  501.             Is 1 if detail  mode.  (NOTE:  If the Detail and Speed flags
  502.             are both 0, then data is in Quality mode).
  503.  
  504.          14 inch paper
  505.  
  506.             is 1 if 14 inch paper length.
  507.  
  508.          5.5 inch paper
  509.  
  510.             is 1 if 5.5 inch  paper length.  (NOTE: If the 14 inch and 5
  511.             inch flags are both 0, then paper length is 11 inch).
  512.  
  513.          paper present
  514.  
  515.             is 1 if paper is present at scanner (should be always 1).
  516.  
  517.  
  518.  
  519.  
  520.  
  521. Alan R. Katz                                                    [page 9]
  522.  
  523.  
  524.                                                                         
  525. DECODING FACSIMILE DATA                                          RFC 798
  526. IV. The Setup Block and the Data Header                                 
  527.  
  528.  
  529.  
  530.       Spare:
  531.  
  532.          These 5 bits can be any value.
  533.  
  534.       Multi-page:
  535.  
  536.          1 if multi page mode
  537.  
  538.       Rest of data of set-up block:
  539.  
  540.          The above  fields are followed by twenty 0 bits and the rest of
  541.          the 512 bits of the block are alternating 0's and 1's.
  542.  
  543.    There  are a number of important points to be remembered in regard to
  544.    the header  of a data block.   First  of all,  the  data  count,  the
  545.    x-position, and the black and white run sizes must be read IN REVERSE
  546.    ORDER.   The reason for this is that the fax machine sends these bits
  547.    in reverse  order.  However, the sequence number and the state fields
  548.    ARE NOT REVERSED.  In addition to this, each run field in the data IS
  549.    REVERSED.   This reversing  of  the  bits  in  each  n-bit  field  is
  550.    completely  separate  from the reversing  and complementing  of  each
  551.    octet mentioned earlier.
  552.  
  553.    Second, only the first n bits, where n is the value of the data count
  554.    field  (remember its reversed!), of the data is valid, the rest is to
  555.    be ignored.  If n is zero, the whole block is to be ignored.
  556.  
  557.    Third,  if the x position  is beyond where the last block ended, fill
  558.    the space  between  where  the last block  ended  and the  current  x
  559.    postion  with white (0's).  If the x postition is less then where the
  560.    last block ended,  replace  the overlapped  data with the data in the
  561.    new block.   If the x postition  is greater  than 1726, ignore it and
  562.    continue from where the previous block left off.
  563.  
  564.    Fourth,  the black  size,  white  size  (reversed),  and  state  (not
  565.    reversed!)  given in the header  are the correct  values even if they
  566.    disagree with the end of the previous block.
  567.  
  568.    Finally,  the sequence  number  (not reversed)  should  count through
  569.    0,1,2,3.  If it does not, a block is missing.
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579. [page 10]                                                   Alan R. Katz
  580.  
  581.  
  582.  
  583. RFC 798                                          DECODING FACSIMILE DATA
  584.                                                V. The Decoding Algorithm
  585.  
  586.  
  587.  
  588. V.   The Decoding Algorithm
  589.  
  590.    Upon first  glance  at the finite  state  diagram in Figure 1, it may
  591.    seem that it would be difficult  to create a decoding procedure.  For
  592.    example,  if you are in the WW state, and the next bit is a 1, how do
  593.    you know  whether to do a transition to WB or BW?  The answer to this
  594.    is to recognize  that every arc out of the BW state begins with 0 and
  595.    every arc out of WB begins with 1.  Thus, if you are in the WW state,
  596.    and the next  bit is 1,  followed  by a 0,  you know  to go to the BW
  597.    state.   If the next bit is 1, followed by a 1, you know to go to the
  598.    WB state.
  599.  
  600.    In writing  the decoding program it was necessary to have two ways of
  601.    reading the next bit in the data stream.  The first way reads the bit
  602.    and "consumes"  it,  i.e.  increments the bit pointer to point at the
  603.    next bit.   The other  way does not "consume"  it.   Below  are  four
  604.    statements  which show how  to  decode  fax  data.   The  numbers  in
  605.    parentheses  are not to be consumed, that is to say they will be read
  606.    again in making the next transition.
  607.  
  608.       If I am in state BW (2) and the next bits are:
  609.          0 (0):             go to BW
  610.          0111:              go to BB
  611.          010 (1):           go to WB
  612.          0100:              go to WW
  613.  
  614.       If I am in state WB (1) and the next bits are:
  615.          1 (1):             go to WB
  616.          1000:              go to WW
  617.          101 (0):           go to BW
  618.          1011:              go to BB
  619.  
  620.       If I am in state  WW (0),  then  first  go through  the run length
  621.       algorithm, then if the next bits are:
  622.          0:                 go to BB
  623.          1 (0):             go to BW
  624.          1 (1):             go to WB
  625.  
  626.       If I am in state  BB (3),  then  first  go through  the run length
  627.       algorithm, then if the next bits are:
  628.          0:                 go to WW
  629.          1 (0):             go to BW
  630.          1 (1):             go to  WB
  631.  
  632.       For the run length  algorithm,  remember, look at the next n bits,
  633.       where  n is the length  of either  the black  or white  run length
  634.  
  635.  
  636.  
  637. Alan R. Katz                                                   [page 11]
  638.  
  639.  
  640.                                                                         
  641. DECODING FACSIMILE DATA                                          RFC 798
  642. V. The Decoding Algorithm                                               
  643.  
  644.  
  645.  
  646.       word,  REVERSE  the bits,  and  output  that  many  BB's  or  WW's
  647.       (depending  on whether black or white run).  If the field is full,
  648.       increment  the size of the word, and get that many bits more, i.e.
  649.       get the next n+1 bits,  etc.  Also, the run length word length can
  650.       be decremented according to the rules given in section III.
  651.  
  652.       You always  go through the run length even if there is only one WW
  653.       or BB, in this case, the run field will be 0.
  654.  
  655.       Let us look at the first example given in section III.  Suppose we
  656.       want to decode the bits:  110111100010100100100101000...  (we have
  657.       already reversed the run lengths to make things easier).
  658.  
  659.       We are in state  1 (WB)  and the black run length word length is 2
  660.       and the white  length  is 3.   We get these  initial values either
  661.       from the block header,  or by remembering  them from the  previous
  662.       transitions  if this is not the start  of the block.  According to
  663.       our rules, we would parse this string as follows:
  664.  
  665.          1(1) 1011 11 000 1(0) 0100 100 1(0) 0(0) 010(1) 1000...
  666.  
  667.       The numbers  in parentheses  are numbers  that were read  but  not
  668.       "consumed",  thus the next number  in the sequence  is the same as
  669.       the one in parentheses.   First,  we see a 1 and that the next bit
  670.       is a 1,  this  means  that we go to WB.  Then we have a 1011 which
  671.       means  to go to BB.   Then we do a run, we have a 11 followed by a
  672.       000 which  means the black run length gets incremented by 1 (it is
  673.       now 3)  and we get 3 MORE  BB's.   Now we have  a 1 followed  by 0
  674.       which  means  go to BW.   Next a 0100 which is WW.  Then we have a
  675.       run, 100, which means four more WW's.  We keep going like this and
  676.       we get the original  bit pattern  given  in the first  example  of
  677.       section III.
  678.  
  679.       It is important  to always  start fresh  when  dealing  with  each
  680.       block.   There  are many reasons  for this.   The  first  is  that
  681.       sometimes blocks are dropped, and you can recover from this if you
  682.       resynchronize  at the start of each block.  Also, if at the end of
  683.       the previous  block, there is about to be a transition, instead of
  684.       making  it at the beginning  of the next block,  the  fax  machine
  685.       gives  the new state in the header of the next block and goes from
  686.       there.   Thus it is important to always start at whatever state is
  687.       given  in the header,  and to align  yourself  at  the  current  X
  688.       position given there also.
  689.  
  690.       Sometimes,  while decoding a block, a bit pattern will occur which
  691.  
  692.  
  693.  
  694.  
  695. [page 12]                                                   Alan R. Katz
  696.  
  697.  
  698.  
  699. RFC 798                                          DECODING FACSIMILE DATA
  700.                                                V. The Decoding Algorithm
  701.  
  702.  
  703.  
  704.       does not correspond  to any transition.  If this happens, the rest
  705.       of the block may be bad and should be discarded.
  706.  
  707.       The decoding  program decodes the fax data block by block until it
  708.       comes to an END command in the data, or runs out of data.
  709.  
  710. VI.  Program Performance
  711.  
  712.    The L10 NLS program takes about two CPU minutes to run on TOPS20 on a
  713.    DEC KL10 to decode the average document in fine detail mode.  In this
  714.    mode,  the picture  is about  1726 by 2100 pels,  and takes about 204
  715.    disk pages to store.
  716.  
  717.    We have a program  which displays bit maps on an HP graphics terminal
  718.    and have been able to display  portions of documents.  (not all of an
  719.    8.5"  by 11"  document  will fit in the display).   We  can  use  the
  720.    terminal's  zoom capability  to look at very small  portions  of  the
  721.    document.
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.  
  741.  
  742.  
  743.  
  744.  
  745.  
  746.  
  747.  
  748.  
  749.  
  750.  
  751.  
  752.  
  753. Alan R. Katz                                                   [page 13]
  754.  
  755.  
  756.                                                                         
  757. DECODING FACSIMILE DATA                                          RFC 798
  758. References                                                              
  759.  
  760.  
  761.  
  762. References
  763.  
  764.    [1]  Weber,  D.  R.,  "An Adaptive  Run Length  Encoding  Algorithm",
  765.    International   Conference   on  Communications,  ICC-75,  IEEE,  San
  766.    Francisco, California, June 1975.
  767.  
  768.    [2]   Mills,   D.   L.,   "Rapicom   450  Facsimile  Data  Decoding",
  769.    WP2097/MD33E, COMSAT Laboratories, Washington D.C., undated.
  770.  
  771.    [3]  Casner,  S.  L.,   "Faxie",   ISI Internal Memo, USC/Information
  772.    Sciences Institute, February 1980.
  773.  
  774.    [4]  Postel,  Jon,  "Rapicom  450 Facsimile  File Format",  RFC  769,
  775.    USC/Information Sciences Institute, September 1980.
  776.  
  777.  
  778.  
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.  
  793.  
  794.  
  795.  
  796.  
  797.  
  798.  
  799.  
  800.  
  801.  
  802.  
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809.  
  810.  
  811. [page 14]                                                   Alan R. Katz
  812.  
  813.  
  814.  
  815. RFC 798                                          DECODING FACSIMILE DATA
  816.                                                                 Appendix
  817.  
  818.  
  819.  
  820. Appendix
  821.  
  822.    In this appendix  is given  the first portion of the data which comes
  823.    from the fax machine,  this same data in RFC 769 format,  and some of
  824.    this data decoded  into a bitmap.   The data is represented  in octal
  825.    octets.
  826.  
  827.    The following  is data of the form which comes out of the fax machine
  828.    with length and command octets added:
  829.  
  830.       114  70 142 171 330  13 377 377 377 371  53 200   0   5 125 125
  831.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  832.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  833.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  834.       125 125 125 125 125 125 125 125 125 121  21 261 114  71 142 171
  835.       330  40   0 102 326 270 152  42  42  44 111   0  42 151 267 122
  836.       366 110 237 102 211 365 111 171 336  51 244 247 377 377 111 362
  837.       177 377 377 377 377 377 377 377 377 376 104 213 241  41 111 377
  838.       111 337 377 377 377 377 377 377 377 377 377 377 377 163 301 361
  839.       377 377 377 377 360 177  12   0 114  71 142 171 330 141 137 177
  840.       377 344  10   0 160  23 301 160 137 376 204 352 135  27 353 264
  841.         0  70 100   7  20  75   0   0   0   0   0 344   0   0   0   0
  842.         0   0   0   0  34 275   0   0   0   0   0   0   0   0   0   0
  843.         0   0   0   0   7  41 310  34 200   0   0 344   0   0   0  71
  844.        13 331 204   0 114  71 142 171 330 241 137  26 302 160   0  16
  845.       100  71   0 370 270 271   0 162   0  71 174 134 100 162   0  34
  846.       234 200 344   7 156 100   1 310  16 107  43 323 263 220 365 313
  847.       327  57 377 325 331  36  56  47 325 324 344   3 227  40  71  35
  848.       200   1 310   1 313 220   0   0   7 241 330   0   0 137 342 200
  849.       114  71 142 171 330 340  77  40 142 160   0   0   0   0 162  71
  850.        73 162 376 276 234 277 376  67 265 301  16  20 171   1 311 313
  851.       346 377 321  75 256 113 245 377 262 160 136 247  13 251 350 374
  852.       270 236 235 217 136 203 220  75 166 166 364 177 305 366  72 107
  853.        63 330 352 345 313 320  71  34 270  46  57   0
  854.  
  855.    The following is the same data after put into RFC 769 format (with
  856.    each data octet reversed and complemented):
  857.  
  858.       114  70 271 141 344  57   0   0   0 140  53 376 377 137 125 125
  859.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  860.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  861.       125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125
  862.       125 125 125 125 125 125 125 125 125 165 167 162 114  71 271 141
  863.       344 373 377 275 224 342 251 273 273 333 155 377 273 151  22 265
  864.       220 355   6 275 156 120 155 141 204 153 332  32   0   0 155 260
  865.         1   0   0   0   0   0   0   0   0 200 335  56 172 173 155   0
  866.  
  867.  
  868.  
  869. Alan R. Katz                                                   [page 15]
  870.  
  871.  
  872.                                                                         
  873. DECODING FACSIMILE DATA                                          RFC 798
  874. Appendix                                                                
  875.  
  876.  
  877.  
  878.       155   4   0   0   0   0   0   0   0   0   0   0   0  61 174 160
  879.         0   0   0   0 360   1 257 377 114  71 271 141 344 171   5   1
  880.         0 330 357 377 361  67 174 361   5 200 336 250 105  27  50 322
  881.       377 343 375  37 367 103 377 377 377 377 377 330 377 377 377 377
  882.       377 377 377 377 307 102 377 377 377 377 377 377 377 377 377 377
  883.       377 377 377 377  37 173 354 307 376 377 377 330 377 377 377 143
  884.        57 144 336 377 114  71 271 141 344 172   5 227 274 361 377 217
  885.       375 143 377 340 342 142 377 261 377 143 301 305 375 261 377 307
  886.       306 376 330  37 211 375 177 354 217  35  73  64  62 366 120  54
  887.        24  13   0 124 144 207 213  33 124 324 330  77  26 373 143 107
  888.       376 177 354 177  54 366 377 377  37 172 344 377 377   5 270 376
  889.       114  71 271 141 344 370   3 373 271 361 377 377 377 377 261 143
  890.        43 261 200 202 306   2 200  23 122 174 217 367 141 177 154  54
  891.       230   0 164 103 212  55 132   0 262 361 205  32  57 152 350 300
  892.       342 206 106  16 205  76 366 103 221 221 320   1 134 220 243  35
  893.        63 344 250 130  54 364 143 307 342 233  13 377
  894.  
  895.    The following is the first part of the expanded bitmap of this data
  896.    (there are about 4 scan lines here, or 2 pairs of scan lines):
  897.  
  898.       177 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  899.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  900.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  901.       377 377 377 377 377 377 367 377 377 377 377 377 377 377 377 377
  902.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  903.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  904.       337 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  905.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  906.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  907.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  908.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  909.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  910.       377 377 377 377 377 377 377 377 377 377 377 377 377 377 377 377
  911.       377 377 377 377 377 377 377 374   0   4 327 377 377 377 377 377
  912.       374 377 356 377 177   0  10   0 201 200   0   0   0   0 100   0
  913.         0   0   0   0   0   0   1 140   0   0   0   0   0   0   0   0
  914.         0   0   0   0   0   0 204  10   0   0  10   0   0   0 100   0
  915.        20  10   7 250   2   0  57 100 100   2 100 100 164   0  20  21
  916.        31 310 153 137 377 377 377 377 177  32 176 344   2 200 216   0
  917.         4   0 240   0   0  14  70   0   0   0   0   0   2  47 137 336
  918.       137 377 377 377 377 375 377 372  20 140  45 376 377 377 377 237
  919.       377 276 357 377 377 377 227 345 314 175  63 215 202   6 347 143
  920.       377 337 376  70 371 370 352 300 213 373 371 377 377 343  73 334
  921.         0 207 315   3  33 111 377 167 337 377   1 323 365 177 377 177
  922.       377 374 377 135 377 377 365  67 343  55 377 377 377 377 357 377
  923.       377 377 377 377 377 377 203 377 236 175 376 236 337 273 347 377
  924.  
  925.  
  926.  
  927. [page 16]                                                   Alan R. Katz
  928.  
  929.  
  930.  
  931. RFC 798                                          DECODING FACSIMILE DATA
  932.                                                                 Appendix
  933.  
  934.  
  935.  
  936.       376  77 377 377 377 377 377 377 377 377 377 377 300   0   0   0
  937.       200 102 177 377 277 377 377 377 376 377 366 365 173 302  12   0
  938.        40 200   0   0   0   4 100   0   0   0   0   0   0   2   5 354
  939.         0   0   0   0   0   0   0   0   4   0  10   0   0   0 200  10
  940.        40  20   1   0 100   0 140   0  20 210 101 374   3 200 155 304
  941.         0   6 100 103 376   0 120 121  31 332 243 177 377 377 377 377
  942.       377 233 377 354   0 241 217   1  30   0 240   0   0  12 150 202
  943.        40   0   0   0  62  47 157 376 173 373 377 377 377 377 377 377
  944.        20 141 321 376 377 377 377 327 377 376 377 377 377 377 237 216
  945.       316 375 167 215 202   6 300 143 377 237 374  70 175 330 377 304
  946.       255 373 153 377 377 353 377 104   0 267 315 203  13 311 177 377
  947.       377 377   1 223 367 377 373 167 377 376  77 137 377 345 165  67
  948.        43  51 277 377 277 377 357 377 377 377 373 177 377 377 223 377
  949.       366 175 376 234 377 271 347 377 376 157 377 377 377 377 377 377
  950.       377 377 377 377 340   0   0   0   0   0 177 377  37 377 377 377
  951.       377 376 367 357 272 300   2   0   4   0   0   0   0   0   0   0
  952.         0   0   0   0  20   0   1 144   0   0   0   0   0   0   4   4
  953.         0   0 100   2 100  10 201  10   0  20  75   0   0  40 142   0
  954.         0  74 341 234 103   4 157 300   0   2   0 141 372   0   0  20
  955.        30 376  55 277 177 377 377 367 377 371 376 100  15  61  16 200
  956.        30   0  40   0   0   0 311 200  24   0   0   0  62  55 377 316
  957.       367 347 377 357 377 377 377 377 170 305   5 276 377 377 377 357
  958.       377 377 377 377 377 177 377 377 357 177 377  76 207 246 340 147
  959.       376 336 356  10  17 320 105 235 275 377 377 373 377 347 335 317
  960.        50  77 377 353  75 333 377 377 377 377 363 337 343 277 356 171
  961.         7 357  76 216 377 211 207 176 257 217 377 377 367 357 357 277
  962.       377 357 377 377 377 375 367 377 377 377 377 375 377 377 356 377
  963.       366 377 377 377 377 377 377 377 377 377 377 377 340   0   0   0
  964.         0  44 373 377  77 377 377 177 177 377 377 337 376 170 173   0
  965.         0   0 100   0   1  10   0   0   0   0   0 200 160   0 223 160
  966.       300   0   0   0   0   0   0   6 100 220   0   0 140   4   3  30
  967.       121  20 351 300 206  74 167   0  30  64  41 234 172  30 175 300
  968.         4  32   4 345 367 200 103  60 177 372 177 233 377 377 377 377
  969.       376 125 207 210 233  21 364 361 277   1  50  16 140 120  41 335
  970.       377 306 214  10  67 377 373 377 377 377 377 377 377 367 377 377
  971.       377 363 277 377 377 377 377 377 267 177 377 377 377 377 377 237
  972.       377 377 377  77 377 377 355 373
  973.  
  974.  
  975.  
  976.  
  977.  
  978.  
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985. Alan R. Katz                                                   [page 17]
  986.  
  987.