Index: core/fxcodec/codec/fx_codec.cpp |
diff --git a/core/fxcodec/codec/fx_codec.cpp b/core/fxcodec/codec/fx_codec.cpp |
index 6b6c7233880af64cac103bdd12f0597bb501d8e6..fff816c73c4863d960352859f5de6cbb7247d198 100644 |
--- a/core/fxcodec/codec/fx_codec.cpp |
+++ b/core/fxcodec/codec/fx_codec.cpp |
@@ -101,14 +101,160 @@ bool CCodec_BasicModule::RunLengthEncode(const uint8_t* src_buf, |
uint32_t src_size, |
uint8_t** dest_buf, |
uint32_t* dest_size) { |
- return false; |
+ // Handle edge cases |
+ if (src_size == 0) |
+ return false; |
+ if (src_size == 1) { |
+ *dest_buf = FX_Alloc(uint8_t, 3); |
+ (*dest_buf)[0] = 0; |
+ (*dest_buf)[1] = src_buf[0]; |
+ (*dest_buf)[2] = 128; |
+ *dest_size = 3; |
+ return true; |
+ } |
+ |
+ // Worst case: 1 nonmatch, 2 match, 1 nonmatch, 2 match, etc. This becomes |
+ // 4 output chars for every 3 input, plus up to 4 more for the 1-2 chars |
+ // rounded off plus the terminating character. |
+ uint32_t est_size = 4 * src_size / 3 + 4; |
Tom Sepez
2017/01/09 20:18:19
Can we get a better estimate by first rounding up
rbpotter
2017/01/10 20:28:23
Done.
|
+ *dest_buf = FX_Alloc(uint8_t, est_size); |
+ |
+ // Set up pointers. |
+ uint8_t* out = *dest_buf; |
+ uint32_t run_start = 0; |
+ uint32_t run_end = 1; |
+ uint8_t x = src_buf[run_start]; |
+ uint8_t y = src_buf[run_end]; |
+ while (run_end < src_size) { |
Tom Sepez
2017/01/09 20:18:19
I'm having trouble following all of this, maybe it
|
+ uint32_t max_len = run_start + 128 < src_size ? 128 : src_size - run_start; |
Tom Sepez
2017/01/09 20:18:19
nit: maybe std::min(src_size - run_start, 128);
rbpotter
2017/01/10 20:28:23
Done.
|
+ while (x == y && ((run_end - run_start) < max_len - 1)) |
Tom Sepez
2017/01/09 20:18:19
Can max_len be 0 here?
nit: overparenthesized.
rbpotter
2017/01/10 20:28:23
Should not be. run_end is always at least one ahea
|
+ y = src_buf[++run_end]; |
+ // Reached end with matched run. Update variables to expected values. |
Tom Sepez
2017/01/09 20:18:19
nit: maybe blank line here.
rbpotter
2017/01/10 20:28:24
Done.
|
+ if (x == y) { |
+ run_end++; |
+ if (run_end < src_size) |
+ y = src_buf[run_end]; |
+ } |
+ if (run_end - run_start > 1) { // Matched run but not at end of input. |
+ out[0] = 257 - (run_end - run_start); |
+ out[1] = x; |
+ x = y; |
+ run_start = run_end; |
+ run_end++; |
+ if (run_end < src_size) |
+ y = src_buf[run_end]; |
+ out += 2; |
+ continue; |
+ } |
+ // Mismatched run |
+ while (x != y && run_end <= run_start + max_len) { |
+ out[(run_end - run_start)] = x; |
Tom Sepez
2017/01/09 20:18:20
nit: overparenthesized, couple places.
rbpotter
2017/01/10 20:28:24
Done.
|
+ x = y; |
+ run_end++; |
+ if (run_end == src_size) { |
+ if (run_end <= run_start + max_len) { |
+ out[(run_end - run_start)] = x; |
+ run_end++; |
+ } |
+ break; |
+ } |
+ y = src_buf[run_end]; |
+ } |
+ out[0] = run_end - run_start - 2; |
+ out += run_end - run_start; |
+ run_start = run_end - 1; |
+ } |
+ if (run_start < src_size) { // 1 leftover character |
+ out[0] = 0; |
+ out[1] = x; |
+ out += 2; |
+ } |
+ *out = 128; |
+ *dest_size = out + 1 - *dest_buf; |
+ return true; |
+} |
+ |
+namespace A85Encode { |
+static const uint64_t a[4] = {256 * 256 * 256, 256 * 256, 256, 1}; |
Tom Sepez
2017/01/09 20:18:20
Can we put these into an empty namespace up top, l
rbpotter
2017/01/10 20:28:23
Done.
|
+static const uint64_t b[5] = {85 * 85 * 85 * 85, 85 * 85 * 85, 85 * 85, 85, 1}; |
} |
bool CCodec_BasicModule::A85Encode(const uint8_t* src_buf, |
uint32_t src_size, |
uint8_t** dest_buf, |
uint32_t* dest_size) { |
- return false; |
+ // Handle edge cases |
+ if (src_size == 0) { |
+ *dest_size = 0; |
+ return false; |
+ } |
+ |
+ // Worst case: 5 output for each 4 input (+ up to 4 from leftover), + |
+ // 2 character new lines each 75 output chars = 2*5*src/(4*75), + 2 |
Tom Sepez
2017/01/09 20:18:19
nit: this might read clearer without = = 2*5*src/(
rbpotter
2017/01/10 20:28:24
Done.
|
+ // termination chars. May have fewer if there are special "z" chars. |
+ uint32_t est_size = 5 * (src_size / 4) + 4 + src_size / 30 + 2; |
+ *dest_buf = FX_Alloc(uint8_t, est_size); |
+ |
+ // Set up pointers. |
+ uint8_t* out = *dest_buf; |
+ uint32_t pos = 0; |
+ uint32_t line_length = 0; |
+ while (src_size >= 4 && pos < src_size - 3) { |
+ uint64_t val = (uint64_t)(src_buf[pos]) * A85Encode::a[0] + |
Tom Sepez
2017/01/09 20:18:19
nit: casst not needed, we're multiplying a uint8_t
Tom Sepez
2017/01/09 20:18:19
Wouldn't this also fit into a uint32_t ?
rbpotter
2017/01/10 20:28:23
Done.
rbpotter
2017/01/10 20:28:24
Done.
rbpotter
2017/01/10 20:28:24
Changed this to shifts, but had to keep the cast t
Tom Sepez
2017/01/10 21:08:41
Right. When we go to shifts, we lose the other bi
|
+ (uint64_t)(src_buf[pos + 1]) * A85Encode::a[1] + |
+ (uint64_t)(src_buf[pos + 2]) * A85Encode::a[2] + |
+ (uint64_t)(src_buf[pos + 3]); |
+ pos += 4; |
+ if (val == 0) { // All zero special case |
+ *out = 'z'; |
+ out++; |
+ line_length++; |
+ } else { // Compute base 85 characters and add 33. |
+ uint64_t c1 = val / A85Encode::b[0]; |
Tom Sepez
2017/01/09 20:18:19
I would imagine we just take c = val % 85 and val
rbpotter
2017/01/10 20:28:24
Done. I was trying to avoid calling %, but this is
|
+ val -= c1 * A85Encode::b[0]; |
+ out[0] = (uint8_t)c1 + 33; |
+ uint64_t c2 = val / A85Encode::b[1]; |
+ val -= c2 * A85Encode::b[1]; |
+ out[1] = (uint8_t)c2 + 33; |
+ uint64_t c3 = val / A85Encode::b[2]; |
+ val -= c3 * A85Encode::b[2]; |
+ out[2] = (uint8_t)c3 + 33; |
+ uint64_t c4 = val / A85Encode::b[3]; |
+ val -= c4 * A85Encode::b[3]; |
+ out[3] = (uint8_t)c4 + 33; |
+ out[4] = (uint8_t)val + 33; |
+ out += 5; |
+ line_length += 5; |
+ } |
+ if (line_length >= 75) { // Add a return. |
+ *out = '\r'; |
Tom Sepez
2017/01/09 20:18:19
nit:
*out++ = '\r';
*out++ = '\n';
line_length =
rbpotter
2017/01/10 20:28:23
Done.
|
+ *++out = '\n'; |
+ out++; |
+ line_length = 0; |
+ } |
+ } |
+ if (pos < src_size) { // Leftover bytes |
+ uint64_t val = 0; |
+ uint32_t count = 0; |
+ while (pos < src_size) { |
+ val += (uint64_t)(src_buf[pos]) * A85Encode::a[count]; |
+ count++; |
+ pos++; |
+ } |
+ for (uint32_t i = 0; i < count + 1; i++) { |
+ uint64_t c = val / A85Encode::b[i]; |
+ val -= c * A85Encode::b[i]; |
+ out[i] = (uint8_t)c + 33; |
+ } |
+ out += count + 1; |
+ } |
+ |
+ // Terminating characters. |
+ out[0] = '~'; |
+ out[1] = '>'; |
+ out += 2; |
+ *dest_size = out - *dest_buf; |
+ return true; |
} |
#ifdef PDF_ENABLE_XFA |