1 /* 2 ** DeltaRowCompression.cpp 3 ** Copyright 2005, Michael Pfeiffer, laplace@users.sourceforge.net. 4 ** All rights reserved. 5 ** Distributed under the terms of the OpenBeOS License. 6 */ 7 8 9 #include "DeltaRowCompression.h" 10 11 #include <memory.h> 12 13 #include <SupportDefs.h> 14 15 16 AbstractDeltaRowCompressor::AbstractDeltaRowCompressor(int rowSize, 17 uchar initialSeed) 18 : 19 fSeedRow(new uchar[rowSize]), 20 fSize(rowSize), 21 fInitialSeed(initialSeed) 22 { 23 Reset(); 24 } 25 26 27 AbstractDeltaRowCompressor::~AbstractDeltaRowCompressor() 28 { 29 delete[] fSeedRow; 30 fSeedRow = NULL; 31 } 32 33 34 status_t 35 AbstractDeltaRowCompressor::InitCheck() 36 { 37 if (fSeedRow != NULL) 38 return B_OK; 39 else 40 return B_NO_MEMORY; 41 } 42 43 44 void 45 AbstractDeltaRowCompressor::Reset() 46 { 47 if (fSeedRow != NULL) 48 memset(fSeedRow, fInitialSeed, fSize); 49 } 50 51 52 int 53 AbstractDeltaRowCompressor::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 125 int 126 AbstractDeltaRowCompressor::CalculateSize(const uchar* row, bool updateSeedRow) 127 { 128 return CompressRaw(row, updateSeedRow, false); 129 } 130 131 132 void 133 AbstractDeltaRowCompressor::Compress(const uchar* row) 134 { 135 CompressRaw(row, true, true); 136 } 137 138 139 #ifdef TEST_DELTA_ROW_COMPRESSION 140 141 void 142 test(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 159 int 160 main(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