1
  2#ifndef __842_H__
  3#define __842_H__
  4
  5/* The 842 compressed format is made up of multiple blocks, each of
  6 * which have the format:
  7 *
  8 * <template>[arg1][arg2][arg3][arg4]
  9 *
 10 * where there are between 0 and 4 template args, depending on the specific
 11 * template operation.  For normal operations, each arg is either a specific
 12 * number of data bytes to add to the output buffer, or an index pointing
 13 * to a previously-written number of data bytes to copy to the output buffer.
 14 *
 15 * The template code is a 5-bit value.  This code indicates what to do with
 16 * the following data.  Template codes from 0 to 0x19 should use the template
 17 * table, the static "decomp_ops" table used in decompress.  For each template
 18 * (table row), there are between 1 and 4 actions; each action corresponds to
 19 * an arg following the template code bits.  Each action is either a "data"
 20 * type action, or a "index" type action, and each action results in 2, 4, or 8
 21 * bytes being written to the output buffer.  Each template (i.e. all actions
 22 * in the table row) will add up to 8 bytes being written to the output buffer.
 23 * Any row with less than 4 actions is padded with noop actions, indicated by
 24 * N0 (for which there is no corresponding arg in the compressed data buffer).
 25 *
 26 * "Data" actions, indicated in the table by D2, D4, and D8, mean that the
 27 * corresponding arg is 2, 4, or 8 bytes, respectively, in the compressed data
 28 * buffer should be copied directly to the output buffer.
 29 *
 30 * "Index" actions, indicated in the table by I2, I4, and I8, mean the
 31 * corresponding arg is an index parameter that points to, respectively, a 2,
 32 * 4, or 8 byte value already in the output buffer, that should be copied to
 33 * the end of the output buffer.  Essentially, the index points to a position
 34 * in a ring buffer that contains the last N bytes of output buffer data.
 35 * The number of bits for each index's arg are: 8 bits for I2, 9 bits for I4,
 36 * and 8 bits for I8.  Since each index points to a 2, 4, or 8 byte section,
 37 * this means that I2 can reference 512 bytes ((2^8 bits = 256) * 2 bytes), I4
 38 * can reference 2048 bytes ((2^9 = 512) * 4 bytes), and I8 can reference 2048
 39 * bytes ((2^8 = 256) * 8 bytes).  Think of it as a kind-of ring buffer for
 40 * each of I2, I4, and I8 that are updated for each byte written to the output
 41 * buffer.  In this implementation, the output buffer is directly used for each
 42 * index; there is no additional memory required.  Note that the index is into
 43 * a ring buffer, not a sliding window; for example, if there have been 260
 44 * bytes written to the output buffer, an I2 index of 0 would index to byte 256
 45 * in the output buffer, while an I2 index of 16 would index to byte 16 in the
 46 * output buffer.
 47 *
 48 * There are also 3 special template codes; 0x1b for "repeat", 0x1c for
 49 * "zeros", and 0x1e for "end".  The "repeat" operation is followed by a 6 bit
 50 * arg N indicating how many times to repeat.  The last 8 bytes written to the
 51 * output buffer are written again to the output buffer, N + 1 times.  The
 52 * "zeros" operation, which has no arg bits, writes 8 zeros to the output
 53 * buffer.  The "end" operation, which also has no arg bits, signals the end
 54 * of the compressed data.  There may be some number of padding (don't care,
 55 * but usually 0) bits after the "end" operation bits, to fill the buffer
 56 * length to a specific byte multiple (usually a multiple of 8, 16, or 32
 57 * bytes).
 58 *
 59 * This software implementation also uses one of the undefined template values,
 60 * 0x1d as a special "short data" template code, to represent less than 8 bytes
 61 * of uncompressed data.  It is followed by a 3 bit arg N indicating how many
 62 * data bytes will follow, and then N bytes of data, which should be copied to
 63 * the output buffer.  This allows the software 842 compressor to accept input
 64 * buffers that are not an exact multiple of 8 bytes long.  However, those
 65 * compressed buffers containing this sw-only template will be rejected by
 66 * the 842 hardware decompressor, and must be decompressed with this software
 67 * library.  The 842 software compression module includes a parameter to
 68 * disable using this sw-only "short data" template, and instead simply
 69 * reject any input buffer that is not a multiple of 8 bytes long.
 70 *
 71 * After all actions for each operation code are processed, another template
 72 * code is in the next 5 bits.  The decompression ends once the "end" template
 73 * code is detected.
 74 */
 75
 76#include <linux/module.h>
 77#include <linux/kernel.h>
 78#include <linux/bitops.h>
 79#include <linux/crc32.h>
 80#include <asm/unaligned.h>
 81
 82#include <linux/sw842.h>
 83
 84/* special templates */
 85#define OP_REPEAT	(0x1B)
 86#define OP_ZEROS	(0x1C)
 87#define OP_END		(0x1E)
 88
 89/* sw only template - this is not in the hw design; it's used only by this
 90 * software compressor and decompressor, to allow input buffers that aren't
 91 * a multiple of 8.
 92 */
 93#define OP_SHORT_DATA	(0x1D)
 94
 95/* additional bits of each op param */
 96#define OP_BITS		(5)
 97#define REPEAT_BITS	(6)
 98#define SHORT_DATA_BITS	(3)
 99#define I2_BITS		(8)
100#define I4_BITS		(9)
101#define I8_BITS		(8)
102#define CRC_BITS	(32)
103
104#define REPEAT_BITS_MAX		(0x3f)
105#define SHORT_DATA_BITS_MAX	(0x7)
106
107/* Arbitrary values used to indicate action */
108#define OP_ACTION	(0x70)
109#define OP_ACTION_INDEX	(0x10)
110#define OP_ACTION_DATA	(0x20)
111#define OP_ACTION_NOOP	(0x40)
112#define OP_AMOUNT	(0x0f)
113#define OP_AMOUNT_0	(0x00)
114#define OP_AMOUNT_2	(0x02)
115#define OP_AMOUNT_4	(0x04)
116#define OP_AMOUNT_8	(0x08)
117
118#define D2		(OP_ACTION_DATA  | OP_AMOUNT_2)
119#define D4		(OP_ACTION_DATA  | OP_AMOUNT_4)
120#define D8		(OP_ACTION_DATA  | OP_AMOUNT_8)
121#define I2		(OP_ACTION_INDEX | OP_AMOUNT_2)
122#define I4		(OP_ACTION_INDEX | OP_AMOUNT_4)
123#define I8		(OP_ACTION_INDEX | OP_AMOUNT_8)
124#define N0		(OP_ACTION_NOOP  | OP_AMOUNT_0)
125
126/* the max of the regular templates - not including the special templates */
127#define OPS_MAX		(0x1a)
128
129#endif