RFC 8478, "Zstandard Compression and the application/zstd Media Type", October 2018

Note: This RFC has been obsoleted by RFC 8878

Errata ID: 6303
Status: Held for Document Update
Type: Technical
Publication Format(s) : TEXT
Reported By: Sean Bartell
Date Reported: 2020-10-07
Held for Document Update by: Barry Leiba
Date Held: 2020-10-08

Section 3.1.1.5 says:

The newest offset takes the lead in offset history, shifting others
back (up to its previous place if it was already present).  This
means that when Repeated_Offset1 (most recent) is used, history is
unmodified.  When Repeated_Offset2 is used, it is swapped with
Repeated_Offset1.  If any other offset is used, it becomes
Repeated_Offset1, and the rest are shifted back by 1.

It should say:

The newest offset takes the lead in offset history, shifting others
back (up to its previous place if the new offset is a repeat offset).
This means that when the new offset is a repeat offset referring to
Repeated_Offset1 (most recent), history is unmodified.
When the new offset is a repeat offset referring to Repeated_Offset2,
it is swapped with Repeated_Offset1.  In any other situation, the new
offset becomes Repeated_Offset1 and the rest are shifted back by 1.

Note that if a non-repeat offset happens to match one of the
Repeated_Offset values, it is treated just like any other non-repeat
offset; all the Repeated_Offset values are shifted back by 1.

The following code demonstrates how an offset_value is decoded into
a NewOffset and the Repeated_Offset values are updated.

if offset_value <= 3:
    if literal_length == 0:
        offset_value = offset_value + 1
    if offset_value == 1:
        NewOffset = Repeated_Offset1
    elif offset_value == 2:
        NewOffset = Repeated_Offset2
        Repeated_Offset2 = Repeated_Offset1
        Repeated_Offset1 = NewOffset
    elif offset_value == 3:
        NewOffset = Repeated_Offset3
        Repeated_Offset3 = Repeated_Offset2
        Repeated_Offset2 = Repeated_Offset1
        Repeated_Offset1 = NewOffset
    elif offset_value == 4:
        NewOffset = Repeated_Offset1 - 1
        if NewOffset == 0:
            # corrupted input
            NewOffset = 1
        Repeated_Offset3 = Repeated_Offset2
        Repeated_Offset2 = Repeated_Offset1
        Repeated_Offset1 = NewOffset
elif offset_value > 3:
    NewOffset = offset_value - 3
    Repeated_Offset3 = Repeated_Offset2
    Repeated_Offset2 = Repeated_Offset1
    Repeated_Offset1 = NewOffset

Notes:

Change the explanation of how Repeated_Offset values are updated in order to match the reference implementation. See https://github.com/facebook/zstd/issues/2346

Report New Errata