Add postscript path

core/fxcodec/codec/fx_codec.cpp

 // Copyright 2014 PDFium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
 
 #include "core/fxcodec/fx_codec.h"
 
 #include <cmath>
 #include <memory>
@@ skipping 83 matching lines @@
 }
 
 uint8_t* CCodec_ScanlineDecoder::ReadNextLine() {
   return v_GetNextLine();
 }
 
 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 src_size to a multiple of 3,
eg.

est_size = 4 * ((src_size + 2) / 3) + 1

[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's clearer as a state machine
where we pick up one new byte on each iteration and do something.  Maybe not. 
Hmm.

+    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 ahead of run_start, so since
run_end < src_size, run_start + 1 < src_size, so src_size - run_start > 1. The
case of a length 1 input is handled above to prevent a possible issue with this,
and leftover single bytes are handled after the loop.

+      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, lose the static, and use more
descriptive names?

[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/(4*75), and if we wrote "plus"
instead of "+" in the comment.

[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 by a uint64_t, which will
promote to uint64_t.  Also, can't we just assemble this with some shifts rather
than multiplying?

[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 to make that work.

[Tom Sepez, 2017/01/10 21:08:41]

Right.  When we go to shifts, we lose the other big unsigned operand, so the
default promotion of uint8_t will now fit into a signed int, and we may end up
shifting into a sign bit ... 

+                   (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 = val / 85 at each step rather
using these big constants.  We may have to assign in the opposite order ...

[rbpotter, 2017/01/10 20:28:24]

Done. I was trying to avoid calling %, but this is a lot cleaner.

+      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 = 0;

[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
 CFX_DIBAttribute::CFX_DIBAttribute()
     : m_nXDPI(-1),
       m_nYDPI(-1),
       m_fAspectRatio(-1.0f),
       m_wDPIUnit(0),
       m_nGifLeft(0),
       m_nGifTop(0),
@@ skipping 201 matching lines @@
                                            int width,
                                            int height,
                                            int nComps,
                                            int bpc) {
   auto pDecoder = pdfium::MakeUnique<CCodec_RLScanlineDecoder>();
   if (!pDecoder->Create(src_buf, src_size, width, height, nComps, bpc))
     return nullptr;
 
   return std::move(pDecoder);
 }