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