Internet-Draft Packed CBOR: Table permutations July 2024
Amsüss Expires 30 January 2025 [Page]
Workgroup:
cbor
Internet-Draft:
draft-amsuess-cbor-packed-shuffle-00
Published:
Intended Status:
Standards Track
Expires:
Author:
C. Amsüss

Packed CBOR: Table permutations

Abstract

Packed CBOR is a compression mechanism for Concise Binary Object Representation (CBOR) that can be used without a decompression step. This document introduces a means for altering configured tables to optimize the use of efficient encoding points by shuffling around entries in the packing tables.

About This Document

This note is to be removed before publishing as an RFC.

The latest revision of this draft can be found at https://chrysn.codeberg.page/packed-shuffle/draft-amsuess-cbor-packed-by-reference.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-amsuess-cbor-packed-shuffle/.

Discussion of this document takes place on the CBOR Working Group mailing list (mailto:cbor@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/cbor/. Subscribe at https://www.ietf.org/mailman/listinfo/cbor/.

Source for this draft and an issue tracker can be found at https://codeberg.org/chrysn/packed-shuffle.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 30 January 2025.

Table of Contents

1. Introduction

[ See abstract. ]

This document uses the "CPA" convention of [I-D.bormann-cbor-draft-numbers]. If it reaches the RFC editing stage, as IANA processes the IANA Considerations, this note is to be removed, and all occurrences of "CPA" will have been replaced with allocated numbers.

2. Setting up the tables by reference

CBOR tag CPA115 describes a permutation of the CBOR packing tables around a rump. Unlike tags CPA113 and most other table setup tags, it does not add items; instead, it modifies the table such that items with very short encoded lengths (most efficient are the first 16 items of the shared table, and the first item of the argument items in straight use, and the first 8 items of the inverted items) can be used even when they were not originally assigned to those positions.

Without excluding others, there are two groups of use cases envisioned:

Packed-Shuffle = #6.<cpa115>([
    shuffle-shared,
    ?shuffle-argument,
    rump])
rump = any
shuffle-shared = shuffle
shuffle-argument = shuffle
shuffle = [+(offset, ?length)]
offset = uint
length = nint

cpa115 = 115   ; preliminary value, see IANA considerations

2.1. Permutation semantics

Inside the rump, each table has a permutation applied compared to the outer table, described in the suffle-shared value for the shared table, and in the shuffle-argument value for the argument table (which defaults to the identical permutation).

The applied permutations are described in inverse (so that a table index used in the rump gets mapped to a table index outside this tag): The item shuffle consecutively lists the lowest items of the inner table by indicating their postions in the outer table. A negative number indicates that a group of in total (1 - length) items are included consecutively starting with the item before the negative number. This creates a kind of run-length encoding. At the end of the shuffle array, all items that were not referenced are appended in their original sequence from the outer table.

An inner index can be calculated in a way suitable to constrained systems by applying the algorighm in Appendix A.

2.2. Examples

Outer table:
 A B C D E F G H

Permutation CBOR item:
 [1 / pick the "B" /, 4 / pick the "E" /, -2 / "3 items" /]

Inner table:
 B E F G A C D H
Figure 1: Single permutation illustrated
1113([
  ["tick.", "tock.", "tickety."],
  ["The clock goes ", "And it goes "],
    [
    [
      6(simple(0)), / "The clock goes tick." /
      6(simple(1)), / "The clock goes tock." /
      224(simple(2)), / "And it goes tickety." /
      6(simple(1)), / "The clock goes tock." /
    ]
    115([[], [1], [
      / The argument table is now:
        ["And it goes ", "The clock goes "]
      /
      6(simple(0)), / "And it goes tick." /
      6(simple(1)), / "And it goes tock." /
      6(simple(2)), / "And it goes tickety." /
      6(simple(1)), / "And it goes tock." /
    ]]),
    [
      6(simple(1)), / "The clock goes tock." /
    ]
  ]
])
Figure 2: Using permutations to make the 6() straight argument available.

Note that in the tick/tock example, using 6() over 224() saves just 1 byte, whereas the setup around tag CPA115 costs 6 bytes. This particular use would break even at 6 uses of tag 6.

3. Security Considerations

[ I don't think there's anything to add? ]

The security considerations of [I-D.ietf-cbor-packed] apply.

4. IANA Considerations

4.1. CBOR Tags Registry

In the registry "CBOR Tags", IANA is requested to allocate one tag:

  • Tag: CPA115

  • Data item: Array [shuffle-shared, ?shuffle-argument, rump]

  • Semantics: "Packed CBOR: table permutation"

  • Reference: This document

5. References

5.1. Normative References

[I-D.bormann-cbor-draft-numbers]
Bormann, C., "Managing CBOR numbers in Internet-Drafts", Work in Progress, Internet-Draft, draft-bormann-cbor-draft-numbers-03, , <https://datatracker.ietf.org/doc/html/draft-bormann-cbor-draft-numbers-03>.
[I-D.ietf-cbor-packed]
Bormann, C. and M. Gütschow, "Packed CBOR", Work in Progress, Internet-Draft, draft-ietf-cbor-packed-12, , <https://datatracker.ietf.org/doc/html/draft-ietf-cbor-packed-12>.

5.2. Informative References

[I-D.amsuess-cbor-packed-by-reference]
Amsüss, C., "Packed CBOR: Table set up by reference", Work in Progress, Internet-Draft, draft-amsuess-cbor-packed-by-reference-02, , <https://datatracker.ietf.org/doc/html/draft-amsuess-cbor-packed-by-reference-02>.

Appendix A. Example implementation

The following algorithm illustrates how table lookup can be implemented without the need for variable size storage per compression table.

An implementation in fixed memory is expected to accommodate up to a fixed size of nested table setup tags. When parsing the shuffle item, if may calculate early_item_count and store it for later use, along with a reference to the position of the shuffle table, through which it iterates again for every item to be unpacked.

def early_item_count(shuffle):
    count = 0
    for (offset, length) in shuffle:
        length = 1 if length is None else 1 - length
        count += length
    return count

def lookup(index, shuffle, outertable):
    shuffle_early_items = early_item_count(shuffle)
    if index < shuffle_early_items:
        for (offset, length) in shuffle:
            length = 1 if length is None else 1 - length
            if index < length:
                return outertable[offset + index]
            index -= length
    else:
        outer_index = index - shuffle_early_items
        for (offset, length) in shuffle:
            length = 1 if length is None else 1 - length
            if offset <= outer_index:
                outer_index += length
        return outertable[outer_index]

Appendix B. Open issues

Whether this document should progress on from the initial version should depend on whether good use cases are identified and whether it outperforms alternative solutions by a sufficient margin.

Author's Address

Christian Amsüss
Austria