PDF.js Source Walkthrough: run_length_stream

Introduction

This is one of the two shortest filters in the "bytes and streams" layer. The subject is RunLengthStream in the worker-side src/core/run_length_stream.js (59 lines).

The previous article, ascii_hex_stream, dealt with "text to binary": two hexadecimal characters combine into one byte, and the decoder only has to remember whether half a byte is pending. This article deals with another plain encoding — run-length encoding. It does not change the character set; instead it compresses "consecutive repeated bytes" into "one header byte plus one sample byte", and "a stretch of non-repeating bytes" into "one header byte plus the bytes as they are".

This encoding does not do general-purpose compression in PDF. The specification lists it under RunLengthDecode, and it mainly serves two kinds of data: bitmap images converted from TIFF, fax or scanners in the early days, and mask images that are large areas of one colour. Such data is characterised by "lots of repetition" — a single row often contains hundreds of identical 0 or 255 values, so run-length encoding pays off handsomely. Conversely, wrapping RLE around text that Flate already compressed is nearly pointless, which is why it rarely appears in the output of modern generators.

Its entry point is likewise a single line:

        case "RL":
        case "RunLengthDecode":
          return new RunLengthStream(stream, maybeLength);

From Parser.makeFilter. Unlike ASCIIHex, there is no separate "scan an inline image" branch here: the RLE end marker is a byte value, and it cannot be located safely by text scanning the way a greater-than sign can. So if an inline image ever does use RunLengthDecode, it goes through the generic terminator search.

Its coding unit is a "run": one run produces at most 128 bytes and at least 1 byte. Each readBlock expands exactly one run and does no looping for the caller's requested amount — the loop lives in the base class.

In one sentence, its job: read a header byte and the sample right after it, copy or repeat the sample into the output buffer according to the run type, and stop immediately at the end byte.

Module Overview

run_length_stream.js is only 59 lines; after the copyright header and the import, there are just two methods:

The data path can be written as:

Encoded bytes (header byte + data bytes)
  → RunLengthStream.readBlock     (this file, one run per call)
  → DecodeStream.buffer           (output buffer, appends 1 to 128 bytes per call)
  → getBytes / getByte            (driven in a loop until the caller's amount is reached)
  → image decoder / Lexer

Compared with ASCIIHex there is no input state carried across blocks. The header, the sample and the data of every run are all read within a single readBlock; the only thing shared between blocks is the output buffer. That difference directly explains why one class needs a firstDigit field and the other needs nothing at all.

readBlock likewise ignores decoderOptions. RLE has no tunable parameters; all information is in the header byte.

Constructor: Why the Size Hint Is Not Scaled

The constructor method

class RunLengthStream extends DecodeStream {
  constructor(str, maybeLength) {
    super(maybeLength);
 
    this.stream = str;
    this.dict = str.dict;
  }

There are only three effective lines in the constructor, and compared with ASCIIHex's constructor two things are missing: size scaling and a state field.

First, why the size hint is not scaled. ASCIIHex output never exceeds half the input and ASCII85 is about four fifths, so both multiply /Length by a factor to bring the first allocation closer to the real output. RLE has no fixed ratio:

Within a single file the expansion ratio can jump from 0.5 all the way to 64. Any fixed factor fails at one end: multiplying by 0.5 makes repeat-heavy streams grow the buffer over and over, while multiplying by 2 makes copy-heavy streams occupy twice the memory from the start. With no reliable prior, do not guess.

maybeLength therefore serves only as the initial capacity hint for DecodeStream, raised to the smallest power of two no smaller than it. Repeat-heavy data may need far more than that, but the geometric growth in ensureBuffer catches up. This is the same principle as in ASCIIHex: the hint only affects the first allocation, and correctness comes from growth.

Second, why no state field is needed. ASCIIHex input can be cut in the middle of a character, so half a byte must be kept. RLE input is measured in runs, and all bytes of a run are read within one readBlock; upstream getBytes itself crosses blocks transparently, so the decoder never sees a "run cut in half". With nothing to carry across calls, the constructor is left with two assignments.

this.dict = str.dict is still necessary. RLE is often used for images, and the downstream decoder needs entries such as /Width, /Height and /BitsPerComponent; the dictionary must be passed along the filter chain, or the image cannot be interpreted.

Design note: The value of a size hint depends on how deterministic the encoding is. Encodings with a clear output bound can scale the hint; encodings whose bound depends strongly on the data cannot. The choice here is not an omission but an admission of "we do not know", handing the uncertainty to the growth strategy.

readBlock: Expanding One Run per Call

The readBlock method

  readBlock() {
    // The repeatHeader has following format. The first byte defines type of run
    // and amount of bytes to repeat/copy: n = 0 through 127 - copy next n bytes
    // (in addition to the second byte from the header), n = 129 through 255 -
    // duplicate the second byte from the header (257 - n) times, n = 128 - end.
    const repeatHeader = this.stream.getBytes(2);
    if (repeatHeader.length < 2 || repeatHeader[0] === 128) {
      this.eof = true;
      return;
    }
 
    let buffer;
    let bufferLength = this.bufferLength;
    let n = repeatHeader[0];

The comment at the top of the method is the full specification: the header byte decides the run type and length, and the second byte is the sample. Once that comment is understood, the rest of the code is almost a line-by-line translation.

The first action is this.stream.getBytes(2). Why read two bytes at once instead of reading the header and then the sample on demand? Because the second byte is needed in both run types:

• In a copy run it is the first byte to be copied, and the header's n counts only the extra bytes after it.
• In a repeat run it is the value being repeated.

Since both cases need it, reading two bytes merges "fetch the header" and "fetch the sample" into one upstream call, saving one call and one truncation check.

repeatHeader.length < 2 covers two situations: upstream is fully exhausted, or only one byte remains. Whether that leftover byte is the end marker or not, it cannot form a complete run, so everything goes to eof and no data is produced.

repeatHeader[0] === 128 is the only end value in the specification. The check comes before allocating the buffer, because an end run needs no output; calling ensureBuffer first would grow the buffer for a run that does not exist.

buffer is declared with let rather than const because it comes from ensureBuffer and may be a new array. bufferLength is copied into a local variable to reduce property accesses inside the method, the same practice as in ASCIIHex.

n first takes the raw header value and is interpreted later by type. There is no validity check on n at all: every value from 0 to 255 has a definite meaning, so there is no such thing as an illegal header.

readBlock handles exactly one run per call and never loops to fill the buffer. The reason is that the base class already does the looping: DecodeStream.getBytes calls it repeatedly until enough bytes are collected for the caller or eof is reached. With the loop in the base class, a subclass only has to guarantee that "one call either produces at least one byte or sets eof".

Design note: One method, one job. The semantics of readBlock are compressed into "expand one run", so it does not need to know how many bytes the caller wants, nor handle the remnants of "half a run". Everything that spans calls is left to the output buffer.

Header Byte Semantics

The header byte divides the one-byte space into three contiguous, gapless segments:

In a copy run, n means "the number of extra bytes beyond the sample". With n equal to 0, a run produces just one byte, the sample right after the header; with n equal to 127 it produces 128 bytes. A copy run consumes one more input byte than its output length because of the header byte.

A repeat run's length is 257 minus the header byte. Header 255 gives 2, header 129 gives 128. This reverse counting is not arbitrary: it is the result of mapping "signed negative numbers" onto unsigned bytes. PackBits uses -1 to -127 for repeat lengths 2 to 128, and reading those signed numbers as two's complement gives exactly 255 down to 129. The PDF specification inherited that mapping, so the smaller the header value, the more repetitions.

128 is reserved for the end, which neatly fills the gap between the two segments. By 257 - 128 it would be 129, beyond the 128-byte limit of a single run, so this value could never represent a legal repeat length anyway. Defining it as the end marker wastes no coding space and makes "stop when the header byte equals 128" a rule that needs no lookup table.

Both types cap a run at 128 bytes. The cap is no coincidence: it guarantees that no run needs two bytes to express its length, and that every header value is used effectively. The price is that long runs must be split, so 300 identical bytes become three runs of 128, 128 and 44.

Design note: One byte encodes both "type" and "length", using range partition rather than flag bits. Copy runs count forward, repeat runs count backward in two's-complement fashion, and the two ranges meet end to end with a single end value between them. This layout leaves the decoder with a single comparison.

Copy Runs: n Less Than 128

if (n < 128) {
  // copy n bytes
  buffer = this.ensureBuffer(bufferLength + n + 1);
  buffer[bufferLength++] = repeatHeader[1];
  if (n > 0) {
    const source = this.stream.getBytes(n);
    buffer.set(source, bufferLength);
    bufferLength += n;
  }
}

Expanding a copy run is almost pure memory copying.

ensureBuffer(bufferLength + n + 1) grows the capacity once to "existing output plus this run's output". The output is exactly n + 1 bytes: one sample plus the following n. Growth happens only here; the writes afterwards never check capacity.

The sample byte is written first: buffer[bufferLength++] = repeatHeader[1]. At this point buffer is already the value returned by ensureBuffer, so even if growth replaced the array, the write goes into the new one. The order cannot be reversed: taking the old reference first and growing afterwards would put the byte into an abandoned buffer.

if (n > 0) is a small optimisation. With n equal to 0 there is no need to ask upstream for data, so the run ends right away and one getBytes(0) call is saved. In DecodeStream, getBytes(0) means "read to the end"; without this check the whole remaining stream would be pulled in, which is completely wrong semantically. The branch is not optional defensive code; it is mandatory.

buffer.set(source, bufferLength) copies the whole view returned by upstream into the output buffer at the given position. source may be a subarray pointing into the upstream buffer; set copies it byte by byte into the output and the two arrays do not affect each other. No loop and no spread operator here — a native bulk copy is far faster than byte-by-byte JavaScript.

bufferLength += n uses the requested amount n, not source.length. Normally getBytes(n) returns exactly n bytes; if upstream runs out early it may return fewer. Advancing by n in that case steps past the data actually written, leaving a gap at the tail.

This is the only "optimistic" spot in the method. Advancing by n steps past the data actually written, and the extra positions stay 0: the buffer is zero-filled when allocated, and bufferLength only grows, so those positions are never written. Truncated input therefore does not raise an error; it produces bytes whose "length is computed from the run and whose tail is all zeros". The next readBlock calls getBytes(2) and gets zero or one byte, immediately sets eof, and the read loop stops. Real corruption lives in a truncated file, where no decoding strategy can restore the data and whether the tail is correct no longer matters.

Design note: A copy run is essentially a memcpy. The decoder performs only two writes: one single byte and one bulk copy. There is no per-byte loop, so even in the worst case of a 128-byte run the JavaScript overhead is a constant.

Repeat Runs: n Greater Than or Equal to 128

    } else {
      n = 257 - n;
      buffer = this.ensureBuffer(bufferLength + n + 1);
      buffer.fill(repeatHeader[1], bufferLength, bufferLength + n);
      bufferLength += n;
    }
    this.bufferLength = bufferLength;

A repeat run takes only three lines, but the information density is high.

n = 257 - n restores the reverse count into a repetition count. Header 129 becomes 128, 255 becomes 2. The subtraction also switches n from "header semantics" to "output length semantics", so the two lines that follow no longer need to distinguish types.

ensureBuffer(bufferLength + n + 1) keeps the copy-run expression, allocating one extra byte. A repeat run really needs only n bytes, and the extra position is never written. This keeps the growth expression identical in both branches; it costs at most one byte and saves the reader from switching between two formulas.

buffer.fill(repeatHeader[1], bufferLength, bufferLength + n) is the core. Uint8Array.fill takes a half-open range: the start is included, the end is not, so it fills exactly n positions. This is a native memory fill, equivalent to memset, with no loop in JavaScript.

Two concrete header bytes:

The first row is the typical shape of "a large area of one colour": two bytes become 128 bytes, a 64-fold expansion. An all-white 1-bit mask image may compress to just a few dozen bytes.

After bufferLength += n, the end of the method writes back this.bufferLength once. Both branches converge there, avoiding duplicated assignments inside the branches.

Design note: A repeat run does not copy the sample; it only fills. Between fill and set, all writes of both run types are covered, and the decoder has no byte-by-byte path at all. Handing the work to native array methods is the main reason short filters still run fast enough.

A Full Expansion of One Data Set

Walking through the encoded bytes one at a time makes run boundaries clearer than an abstract description. Suppose upstream provides these eight bytes:

03 41 42 43 44 81 00 80

First readBlock:

1. getBytes(2) returns 03 and 41.
2. Header 3 is below 128, so it is a copy run; the output length is 3 plus 1, that is 4.
3. Write sample 0x41 first, then getBytes(3) returns 42 43 44 and the whole segment is copied.
4. bufferLength goes from 0 to 4, and the upstream position reaches 5.

Second call:

1. getBytes(2) returns 81 and 00.
2. Header 129 is greater than or equal to 128, so it is a repeat run; 257 - 129 equals 128.
3. fill writes 0x00 into 128 positions of the output buffer.
4. bufferLength goes from 4 to 132, and the upstream position reaches 7.

Third call:

1. Only 80 remains upstream, so getBytes(2) returns a view of length 1.
2. repeatHeader.length < 2 matches first, eof is set directly, and nothing is produced.
3. bufferLength stays at 132.

The whole process can be laid out as a table:

The first eight bytes of the output buffer are 41 42 43 44 00 00 00 00, followed by another 124 00s.

This table also explains what "read on demand" means. If the caller asks for only 4 bytes, getBytes(4) is satisfied after the first readBlock, and the second and third runs are never expanded; the remaining bytes stay upstream until the next read. If the caller asks for 200 bytes at once, all three calls run and 132 bytes are returned, not an error and not zero padding.

The third call has one more easily missed ordering detail: the end marker occupies a single byte, yet the code always requests two. When it happens to be the end of the file, the "fewer than two bytes" test fires before the "equals 128" test. Both paths end in eof, so the order does not affect correctness, but it shows that the header is read "in pairs" rather than "by meaning".

Design note: Decoding progress is decided by run boundaries, not by the number of bytes the caller requested. A request for 4 bytes expands one run; a request for 200 expands until eof; the same data can be consumed at any granularity and the state stays consistent.

The Boundary Between the Decoder and Image Consumers

RunLengthDecode is almost exclusively used for images in PDF. That means its output bytes are not handed to Lexer for tokenizing but to an image decoder to be interpreted as pixels. This boundary means the class does not need to understand rows, columns or colour spaces.

this.dict = str.dict is the key line on that boundary. RLE itself never reads the dictionary, but it passes it down intact so the image decoder can obtain /Width, /Height, /BitsPerComponent and /ColorSpace. If this layer dropped the dictionary, the filter chain could still decode but the pixels could not be assembled correctly.

DecodeParms is meaningless for RLE. The RL branch of Parser.makeFilter accepts no params, because the specification defines no parameters for RunLengthDecode. Compare FlateDecode in the same switch: it hands params to PredictorStream. RLE has no comparable horizontal differencing or row-width configuration.

One more easily misunderstood point: RLE runs may cross image row boundaries. Encoding works on the byte stream, and an encoder may happily merge the end of one row with the start of the next into a single run; the decoder does not need to know how wide a row is, it only expands continuously. Splitting into rows is the image decoder's job, with positions determined by /Width and /BitsPerComponent.

In terms of memory, the class holds only "decoded output" at all times. An image decoder usually asks for the whole image, so getBytes keeps driving readBlock and the buffer grows all the way to the full pixel size; growth happens geometrically, so the total copied volume stays linear. For an image dominated by large areas of one colour, the input is small and the output is large, so the growth goes through several doublings, but the cost of each doubling is amortised by the large reads that follow.

Design note: A filter is responsible for bytes, not semantics. RLE does not know what a row, a pixel or a colour space is; it passes the dictionary through untouched, outputs bytes continuously, and leaves interpretation to downstream. This boundary lets one decoder serve any image type.

Output Accumulation and Block Boundaries

readBlock produces one run at a time, but callers usually want a whole stretch of data. Accumulation rests on two things: this.bufferLength and ensureBuffer.

this.bufferLength persists on the object; each readBlock starts writing from it and updates it at the end. The second call therefore sees the previous endpoint, and the output joins up naturally. ensureBuffer allocates a new array only when capacity is insufficient and copies the old contents over wholesale; the logical length is unaffected.

repeatHeader is a view of the upstream buffer and does not become invalid because the output buffer grows. It points at different memory, unrelated to this.buffer. That is also why the "read the header first, then grow" order works: the two bytes read stay valid for the entire method.

How many readBlock calls a single getBytes(1000) needs depends on the shape of the data:

The worst case is "every run produces a single byte". Then each byte read requires one readBlock call, and each call asks upstream for two bytes. Such input is rare in practice: the point of run-length encoding is to shorten repetitions, and if the data has no runs an encoder usually would not choose it. Even so, the cost is only function-call overhead; it never degenerates into quadratic complexity.

Another point worth noting: readBlock never "reads ahead" to the next run. It does not know whether more data follows and does not need to. Whether the header equals 128 and whether upstream still has two bytes can only be determined on the next call. This one-at-a-time rhythm keeps memory usage equal to "decoded output plus one run", independent of the stream length.

Design note: Blocks share output only, never input. Each RLE run is completed within a single call, so the decoder has no "pending state". This is exactly the opposite of ASCIIHex: there a block boundary falls between characters and half a byte must be kept; here a boundary always falls between runs.

End, Truncation, and Fault Tolerance

RLE has no separate end-marker section because the end is simply one value of the header byte. Here are the four ways it can finish:

The first case has a detail: the end byte is a single byte, but the code reads two. If the file happens to end right there, getBytes(2) returns one byte, length < 2 matches first, and repeatHeader[0] === 128 is never evaluated. Both paths give the same result, eof. If bytes follow the end marker, both are read and the second is discarded — it never belonged to this stream anyway.

The second case is real truncation. A header byte plus zero samples cannot form any run, so it can only stop.

The third case is partial data. getBytes(n) returns as much as it can, shortened near the end. The code still advances the logical length by n, as discussed earlier: the tail of the output is padded with zero bytes rather than the length being rolled back. The next call ends immediately, and the caller receives data whose "declared length is computed from the run and whose tail is zeros".

The repeat type has no third case, because it needs only two bytes to complete a run, and those two bytes were read together at the start.

The decoder performs no header validation at all. Every value from 0 to 255 has a definite meaning; there is no such thing as an illegal header, and corrupt data is merely interpreted as some run that produces plausible-looking but wrong bytes. This is a deliberate trade-off: RLE is used almost exclusively for images in PDF, and when an image is corrupt the image decoder above will fail or degrade, so the decoder itself has no reason to maintain a separate set of error codes.

Design note: The header byte is the truth. The decoder stores no "data still owed" and never goes back to validate whether a run made sense; every anomaly converges on the same eof. For a simple encoding that only serves images, that is enough fault tolerance.

Comparison with ASCIIHex

Both filters are short, but their differences happen to cover the two ways of handling a block boundary:

ASCIIHexDecode boundaries fall between characters, so half a byte must be saved; RunLengthDecode boundaries fall between runs, so nothing needs saving. Both end with an "in-band marker": one uses a greater-than sign, the other a specific byte value. The difference is that a greater-than sign almost never occurs naturally in text and can be scanned safely, whereas 0x80 can perfectly well occur inside binary data, so it can only be read sequentially in run order and never scanned in advance.

That is also why inline images get dedicated end-scan functions only for ASCIIHex and ASCII85, while RLE takes the generic path. Whether "scan first, slice later" is possible depends on whether the marker is distinguishable from the data space.

Conclusion

RunLengthStream is PDF.js's run expansion filter: it reads a header byte and a sample, copies or repeats the sample into the output buffer, and the base class's read loop stitches the runs into a continuous byte stream.

Where It Sits in the Overall Chain

In one sentence: upstream provides encoded bytes, readBlock expands one run per call, getBytes stitches runs into continuous data, and the image decoder and parser only look at the result.

Five Design Principles

1. The header byte carries its own type and length. Copy runs use 0 to 127, the end uses 128, repeat runs use 129 to 255; the test needs a single comparison and no extra flag bits.
2. One run, one call. readBlock does not loop internally to reach a length and does not carry input state across calls. Block spanning is solved by the base class's read loop together with the continuously accumulated output buffer.
3. Read the two header bytes first, then the data on demand. Both run types necessarily use the second byte, so merging the reads saves one upstream call and one truncation test; the end and truncation are detected in the same place.
4. Leave bulk writes to native methods. set for copying, fill for repeating; JavaScript only does constant-level scheduling. This is why short filters can still handle large images efficiently.
5. Do not hint an uncertain ratio. The output-to-input ratio ranges from 0.5 to 64, so maybeLength is not scaled and the capacity question is left to geometric growth.

Seen next to the previous article ascii_hex_stream, these two classes form the shortest pair in the filter chain: one splits text into nibbles and reassembles bytes, the other expands bytes by runs. Neither needs a dictionary, a code table or a window, yet together they demonstrate the two extremes of the DecodeStream contract — one has cross-block state, the other has none at all.

StreamPDF design principle: anything that can be handled ahead of time is absolutely not deferred to parse time; the server solves all performance problems once. The browser only fetches and renders the data it must.