1/*
2** DeltaRowCompression.cpp
3** Copyright 2005, Michael Pfeiffer, laplace@users.sourceforge.net.
4** All rights reserved.
5** Distributed under the terms of the MIT License.
6*/
7
8
9#include "DeltaRowCompression.h"
10
11#include <memory.h>
12
13#include <SupportDefs.h>
14
15
16AbstractDeltaRowCompressor::AbstractDeltaRowCompressor(int rowSize,
17	uchar initialSeed)
18	:
19	fSeedRow(new uchar[rowSize]),
20	fSize(rowSize),
21	fInitialSeed(initialSeed)
22{
23	Reset();
24}
25
26
27AbstractDeltaRowCompressor::~AbstractDeltaRowCompressor()
28{
29	delete[] fSeedRow;
30	fSeedRow = NULL;
31}
32
33
34status_t
35AbstractDeltaRowCompressor::InitCheck()
36{
37	if (fSeedRow != NULL)
38		return B_OK;
39	else
40		return B_NO_MEMORY;
41}
42
43
44void
45AbstractDeltaRowCompressor::Reset()
46{
47	if (fSeedRow != NULL)
48		memset(fSeedRow, fInitialSeed, fSize);
49}
50
51
52int
53AbstractDeltaRowCompressor::CompressRaw(const uchar* row, bool updateSeedRow,
54	bool updateDeltaRow)
55{
56	int index = DiffersIndex(row, 0);
57	if (index == -1) {
58		// no differences
59		return 0;
60	}
61
62	fUpdateDeltaRow = updateDeltaRow;
63	fDeltaRowIndex = 0;
64
65	int seedRowIndex = 0;
66	do {
67		int length = DiffersLength(row, index);
68
69		// delta starts at index and contains length bytes
70		do {
71			// control byte limits data bytes to 8 bytes
72			int deltaBytes = length;
73			if (length > 8)
74				deltaBytes = 8;
75
76			// calculate offset
77			int totalOffset = index - seedRowIndex;
78			bool needsOffsetBytes = totalOffset > 30;
79			int offset = totalOffset;
80			// control byte limits offset value to 31
81			if (needsOffsetBytes)
82				offset = 31;
83
84			// write control byte (delta bytes bits 5-7; offset bits 0-4)
85			Put(((deltaBytes - 1) << 5) | offset);
86
87			if (needsOffsetBytes) {
88				// write additional offset bytes after control byte
89				// the last offset byte must be less than 255
90				totalOffset -= offset;
91				while (totalOffset >= 255) {
92					Put(255);
93					totalOffset -= 255;
94				}
95
96				Put(totalOffset);
97			}
98
99			// write data bytes
100			for (int i = 0; i < deltaBytes; i ++) {
101				// copy row to seed row and delta row
102				uchar byte = row[index];
103				if (updateSeedRow) {
104					ASSERT (index < fSize);
105					fSeedRow[index] = byte;
106				}
107				Put(byte);
108				index ++;
109			}
110
111			seedRowIndex = index;
112
113			length -= deltaBytes;
114
115		} while (length > 0);
116
117		index = DiffersIndex(row, index);
118
119	} while (index != -1);
120
121	return fDeltaRowIndex;
122}
123
124
125int
126AbstractDeltaRowCompressor::CalculateSize(const uchar* row, bool updateSeedRow)
127{
128	return CompressRaw(row, updateSeedRow, false);
129}
130
131
132void
133AbstractDeltaRowCompressor::Compress(const uchar* row)
134{
135	CompressRaw(row, true, true);
136}
137
138
139#ifdef TEST_DELTA_ROW_COMPRESSION
140
141void
142test(AbstractDeltaRowCompressor* compressor, uchar* row) {
143	int size = compressor->CalculateSize(row);
144	printf("size %d\n", size);
145
146	if (size > 0) {
147		uchar* buffer = new uchar[size];
148		compressor->Compress(row, buffer, size);
149		for (int i = 0; i < size; i ++) {
150			printf("%2.2x ", (int)buffer[i]);
151		}
152		printf("\n");
153		delete buffer;
154	}
155	printf("\n");
156}
157
158
159int
160main(int argc, char* argv[])
161{
162	int n = 5;
163	uchar row1[] = {0, 0, 0, 0, 0};
164	uchar row2[] = {0, 1, 0, 0, 0};
165	uchar row3[] = {1, 1, 0, 2, 2};
166
167	DeltaRowCompressor compressor(n, 0);
168	test(&compressor, row1);
169	test(&compressor, row2);
170	test(&compressor, row3);
171}
172
173#endif // TEST_DELTA_ROW_COMPRESSION
174