/* stategen.cpp - State table generator for Counter type PAQ1 archiver.
(C) 2002 Matt Mahoney. mmahoney@cs.fit.edu
This program is free software distributed without warranty
under the terms of the GNU General Public License,
see http://www.gnu.org/licenses/gpl.txt
A Counter state represents two numbers, n0 and n1, using 8 bits, and
the following rule:
Initial state is (0, 0)
If input is a 0, then next state is (n0+1, n1/2+1)
If input is a 1, then next state is (n0/2+1, n1+1)
with the exception that counts less than 2 are not decreased.
There are at most 256 states represented by 8 bits.
For large values of n, an approximate representation is used
with probabilistic increment. The state table needs the following
mappings from the state s:
n0
n1
next state s00 for input 0 if probabilistic increment fails
next state s01 for input 0 if probabilistic increment succeeds
next state s10 for input 1 if probabilistic increment fails
next state s11 for input 1 if probabilistic increment succeeds
probability of increment succeeding on input 0 (x 2^32-1)
probability of increment succeeding on input 1 (x 2^32-1)
Thus the output is 256 records written as a C initialization for
an array of 256 structs with 8 members each. As an optimization
of the target program, the states are ordered by n0+n1 (the
hash replacement priority) except that states for which n0 and
n1 are incremented with probability 1 come first (so that a
table lookup and random number generation can be avoided for
low states).
*/
#include
#include
#include
#include