Internet-Draft GCMF August 2026
Dutta Expires 2 March 2027 [Page]
Workgroup:
Independent Research
Published:
Intended Status:
Experimental
Expires:
Author:
S. Dutta
The ZSMC Co.

General-Purpose Compression via Mathematical Functions (GCMF)

Abstract

This document specifies General-Purpose Compression via Mathematical Functions (GCMF), a lossless compression format that represents sequences of data using mathematical functions and associated parameters.

GCMF attempts to represent a sequence using a compact mathematical representation rather than storing every value explicitly. This document defines the GCMF data format, function types, encoding rules, decoding procedure, and interoperability requirements.

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 2 March 2027.

▲

Table of Contents

1. Introduction

General-Purpose Compression via Mathematical Functions (GCMF) is a lossless compression method that represents data using mathematical functions.

Instead of storing every value in a sequence explicitly, GCMF may store a function and a range over which the function can reproduce the original values.

The objective of GCMF is to reduce the amount of information required to represent sequences that exhibit mathematical regularity, in the spirit of minimum-description-length approaches to modeling such as [J_RISSANEN_1978].

A GCMF encoder MUST evaluate a set of valid candidate representations supported by the implementation and SHOULD select the candidate having the minimum complete encoded length, as described in Section 3.

1.1. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] when, and only when, they appear in all capitals, as shown here.

This document also uses "OPTIONAL" as a structural label within binary layout diagrams (Section 4) to mark a field that is absent under some, but not all, values of a preceding discriminant field (for example, a Function Address or a predefined-function identity). A field so marked is still mandatory whenever the applicable discriminant requires it; "OPTIONAL" in a diagram never means an implementation may omit the field at its own discretion. Section 4.1 identifies, for each representation, which fields are conditional and on what.

2. File Extension and MIME Type

GCMF currently utilizes a working MIME type of application/gcmf. This is not an officially registered MIME type under [RFC2046], or under any current standard or working group as of the publication of this document. It is intended only to identify the file type to adopting implementations.

GCMF also currently utilizes a working file extension of .gcmf. Until formal registration occurs, this extension SHOULD be treated with the same significance as the MIME type above.

3. Function Representation Model

GCMF represents a numerical data sequence as the evaluation of a mathematical function over a finite domain, optionally augmented by a residual function. The original sequence MUST be:

D = d0, d1, ..., d(n-1)

A GCMF encoder MUST attempt to determine a function (f), a domain sequence (X = x0, x1, ..., x(n-1)), and MAY also determine a residual function. For a generalized representation:

d(i) = f(x(i))

For an exact representation:

d(i) = f(x(i)) + r(x(i))

The exact representation is therefore a special case of the generalized representation for which:

r(x) = 0

Let C be the theoretical set of all valid GCMF candidate representations, and let C_I be the subset of candidates that a particular implementation is capable of generating, where C_I is a subset of C. Because a real implementation can only search C_I, its encoder optimization objective is:

C*_I = arg min L(C), for C in C_I

where L(C) is the complete encoded length of candidate C in bytes, as defined in Section 3.1.

An implementation MAY use heuristic, statistical, symbolic, or other candidate-discovery methods. An implementation is not required to discover every mathematically valid representation; consequently an implementation is not required to find C*, the theoretical global optimum over C, and is only required to find C*_I, the best candidate it is able to construct.

A candidate is considered compressive only when its complete encoded representation is smaller than the original input under the source-size comparison defined in Section 3.1.

3.1. Source Size Comparison

For the purpose of determining whether a GCMF representation is compressive, the original input is considered as a sequence of N bytes and has a source size of N bytes.

A GCMF representation is compressive if and only if:

L(C) < N

where L(C) is the complete physical size of the GCMF representation in bytes.

All GCMF structural overhead MUST be included in L(C), including magic numbers, version information, function addresses, parameters, domains, residual data, padding, and all other encoded fields.

An implementation MUST NOT claim compression solely because the mathematical description of the data is shorter than the original data.

4. GCMF Binary Format Specification

This section defines the binary representation of GCMF. A conforming GCMF decoder MUST be capable of parsing all mandatory structure defined in this specification. Unless otherwise stated, all bit fields are packed from the most-significant bit to the least-significant bit.

GCMF is a lossless representation format. A valid GCMF stream MUST decode to exactly the byte sequence represented by the encoded data.

Every GCMF representation is one of exactly two kinds: a LITERAL representation (Section 4.18) or a mathematical representation (Section 4.8 through Section 4.17). A mathematical representation is further one of exactly two kinds: a CUSTOM function representation, in which the function is defined inline by bytecode, or a PREDEFINED function representation, in which the function is identified by Function Address alone and looked up in the registry of Section 4.9. These branches are mutually exclusive: a single representation never contains both a CUSTOM bytecode body and a PREDEFINED parameter body, and never contains both a mathematical body and a LITERAL payload. The field tables in Section 4.8, Section 4.9, and Section 4.18 give the exact, non-overlapping field sequence for each of these three branches; the combined view in Section 4.20 shows them side by side for comparison only and is not itself a fourth, independent layout.

4.1. File Structure

A GCMF file consists of a fixed header followed by a representation-specific payload. The general structure is:

+--------------------------------+
| Magic                | 4 bytes |
+--------------------------------+
| Version               | 1 byte |
+--------------------------------+
| Function Address      | 5 bits |
+--------------------------------+
| Representation Data   | variable, see Sections 4.8, 4.9, 4.18 |
+--------------------------------+
| Physical EOF                   |
+--------------------------------+

The Function Address determines the interpretation of Representation Data. For mathematical representations, Representation Data consists of the function body (either inline CUSTOM bytecode or PREDEFINED parameters), X_start, X_end, BASE, and, when the residual flag is set, the residual representation. For LITERAL, Representation Data consists entirely of the original source bytes after the required alignment padding.

Physical EOF is not encoded as a field or byte; it is the point at which the physical GCMF stream ends, and it terminates the final representation. There is exactly one Magic field and one Physical EOF per file: unlike some of the illustrative field tables later in this section, the file as a whole never repeats the Magic field or contains an in-band EOF marker (see Section 4.19).

The exact fields present after the Function Address depend on the selected function type. The LITERAL function type is an exception and terminates the structured portion of the stream after three padding bits.

4.2. Magic Number

Every GCMF file MUST begin with the following 4 bytes: 0x47 0x43 0x4D 0x46. These bytes correspond to the ASCII string "GCMF". A decoder MUST reject a file whose first 4 bytes do not equal 0x47 0x43 0x4D 0x46.

4.3. Version

Immediately following the magic number is an 8-bit unsigned version field. The version number assigned to this publication is Version 0, written as 0x00.

Future versions MAY use additional version values. A decoder encountering an unsupported version MUST NOT attempt to interpret the remainder of the stream according to an unsupported specification.

4.4. Function Address

The function address is a 5-bit field defined as:

+---+---------+
| 1 |    4    | BITS
+---+---------+
| R | A A A A |
+---+---------+

where R is the residual flag and AAAA is the function type address.

4.4.1. Residual Flag

The most-significant bit MUST be the residual flag, where 0 indicates no residual function is present and 1 indicates a residual function is present.

If R = 1, the residual representation immediately follows the primary mathematical representation according to the residual encoding rules in Section 4.16. R MUST be 0 for LITERAL (Section 4.18).

4.4.2. Function Type Address

The four-bit function type address AAAA selects one of the sixteen function types listed in Table 1. LITERAL with the residual flag set (address 10001) is reserved and MUST be rejected by a conforming decoder unless a future GCMF version explicitly defines semantics for it.

4.5. Bit Packing

The Function Address occupies exactly five bits and MUST NOT automatically consume a complete byte.

The bit immediately following the Function Address is the first bit of the next field unless alignment is explicitly required by the representation.

GCMF-VLI units MAY begin at any bit offset within a bit-packed structure. Implementations MUST therefore provide a bit-level reader and writer for structured GCMF fields.

Where a field is explicitly required to be byte-aligned, zero-valued padding bits MUST be inserted before that field. Padding bits MUST NOT be interpreted as data and MUST be zero.

Unless explicitly specified otherwise, no implicit alignment is performed.

4.6. Variable Length Integer Encoding

GCMF uses a variable-length integer representation called GCMF-VLI. Each encoded unit contains:

+---+-------+
| 1 |   7   | BITS
+---+-------+
| C | VALUE |
+---+-------+

where C = 1 indicates that another VLI unit follows, C = 0 indicates the final VLI unit, and VALUE contains 7 bits of the integer.

The first unit contains the most significant portion of the value. Therefore, GCMF-VLI is a big-endian base-128 representation.

A decoder MUST continue reading VLI units until a unit with C=0 is encountered. A VLI MUST NOT contain unnecessary leading zero payload groups.

4.7. Signed Integer Encoding

Where a mathematical parameter may be negative, GCMF uses ZigZag encoding before GCMF-VLI encoding. For a signed integer n:

Z(n) = 2n,        n >= 0
Z(n) = -2n - 1,   n < 0

The resulting non-negative integer is then encoded using GCMF-VLI. This allows small negative and positive values to have similarly compact representations.

4.8. CUSTOM Function

A CUSTOM function has Function Type Address:

0000

or, when residual data is present:

10000

A CUSTOM representation always carries an inline function body; the Function Length and Function Bytecode fields below are therefore mandatory whenever Function Address selects CUSTOM, and are never present under any other function type. The structure is:

+--------------------------------------------------------------+
| Magic                | 4 bytes (0x47434D46)                  |
+--------------------------------------------------------------+
| Version               | 1 byte (0x00)                        |
+--------------------------------------------------------------+
| Function Address      | 5 bits                                |
+--------------------------------------------------------------+
| Function Length       | variable VLI                         |
+--------------------------------------------------------------+
| Function Bytecode     | Function Length bits                 |
+--------------------------------------------------------------+
| X_start               | variable VLI                         |
+--------------------------------------------------------------+
| X_end                 | variable VLI                         |
+--------------------------------------------------------------+
| Base                  | variable VLI                         |
+--------------------------------------------------------------+
| [Residual]            | present iff R = 1, see Section 4.17  |
+--------------------------------------------------------------+

Physical EOF follows the final field; per Section 4.19 no additional Magic or EOF field is encoded at the end of the representation.

The Function Length specifies the number of bits occupied by the function bytecode, including opcode bits, operand bits, and the END instruction.

The Function Length MUST be sufficient to contain a complete bytecode sequence ending in an END instruction.

The decoder MUST NOT read beyond the declared function length while executing the function.

Any unused bits between the final END instruction and the declared function boundary MUST be zero. A canonical encoder SHOULD emit no unused bits after END.

The function bytecode MUST contain a valid END instruction within the specified function length.

4.9. Predefined Functions

A predefined function does not contain its mathematical definition in the file. The Function Address identifies the mathematical function through the GCMF predefined-function registry. The decoder obtains the function definition from the version-specific registry.

A predefined representation never carries a Function Length or Function Bytecode field; those fields are exclusive to CUSTOM (Section 4.8). Depending on which predefined function is selected, the Function Parameters field itself may be empty: Section 4.9.1 defines five predefined functions (FIBONACCI, FACTORIAL, TRIANGULAR, SQUARE, CUBE) that take no parameters, in which case this field is zero-length and X_start immediately follows the Function Address. A predefined function therefore has the general structure:

+--------------------------------------------------------------+
| Magic                | 4 bytes (0x47434D46)                  |
+--------------------------------------------------------------+
| Version               | 1 byte (0x00)                        |
+--------------------------------------------------------------+
| Function Address      | 5 bits                                |
+--------------------------------------------------------------+
| [Function Parameters] | OPTIONAL, variable -- empty for the   |
|                        | zero-parameter functions listed      |
|                        | above, otherwise per Section 4.9.1   |
+--------------------------------------------------------------+
| X_start               | variable VLI                         |
+--------------------------------------------------------------+
| X_end                 | variable VLI                         |
+--------------------------------------------------------------+
| Base                  | variable VLI                         |
+--------------------------------------------------------------+
| [Residual]            | present iff R = 1, see Section 4.17  |
+--------------------------------------------------------------+

Physical EOF follows the final field; per Section 4.19 no additional Magic or EOF field is encoded at the end of the representation.

Each predefined function MUST have a precisely defined parameter encoding.

4.9.1. Predefined Function Parameter Encoding

Unless otherwise specified, all integer parameters of predefined functions are encoded using GCMF-VLI. Parameters that may be negative MUST use ZigZag encoding before GCMF-VLI encoding.

The predefined functions use the following parameter encodings:

CONSTANT:     c
LINEAR:       a, b
ARITHMETIC:   a, d
GEOMETRIC:    a, r
POLYNOMIAL:   n, a0, a1, ..., an
EXPONENTIAL:  a, b
LOGARITHMIC:  a, b, c
POWER:        a, b, c
MODULAR:      G(x), m
FIBONACCI:    no parameters
FACTORIAL:    no parameters
TRIANGULAR:   no parameters
SQUARE:       no parameters
CUBE:         no parameters

For MODULAR, G(x) is a mathematical function defined by a nested GCMF function representation and m is a positive integer modulus. The nested function G(x) MUST be encoded using the same function representation rules defined by this specification, excluding residual encoding.

The modulus m MUST be encoded as an unsigned GCMF-VLI integer and MUST satisfy m >= 1.

For every domain value x, the decoder first evaluates G(x) and then computes:

F(x) = G(x) mod m

The result of the modulo operation MUST be the unique integer r satisfying 0 <= r < m, where G(x) = qm + r for some integer q.

The MODULAR function MUST NOT contain a residual representation within its nested G(x) function. Recursive MODULAR functions MAY be permitted, provided that the implementation-defined maximum nesting depth is not exceeded.

A decoder MUST reject a MODULAR representation if G(x) is invalid, m is zero, or evaluation of G(x) produces a value outside the supported numerical domain.

All parameters MUST appear in the order specified above. A decoder MUST reject a representation containing missing, malformed, or unexpected parameter data.

4.10. Function Bytecode

GCMF mathematical functions use a stack-based bytecode. Each opcode occupies exactly five bits.

The opcode is immediately followed by its operand, if the opcode requires one. No implicit byte alignment is performed between an opcode and its operand.

For CONST, the operand is a signed GCMF-VLI value. For instructions that do not require an operand, no operand bits are present.

The Function Length counts every bit occupied by the bytecode, including five-bit opcodes and all operand bits. A decoder MUST NOT read beyond the declared Function Length while decoding instructions.

The bytecode MUST contain exactly one terminating END instruction as its logical terminator. A canonical bytecode representation MUST NOT contain instructions after END.

Because opcodes are bit-packed, an operand begins at the bit immediately following the opcode.

4.11. Stack Machine Requirements

A custom function is evaluated independently for every value of x. Before evaluating a new x, the evaluation stack MUST be empty. Each instruction operates on the stack.

For binary operators: [a, b] becomes [a OP b].

For unary operators: [a] becomes [OP(a)].

DUP transforms: [a] becomes [a, a].

X pushes the current domain value.

CONST pushes its encoded constant.

END terminates execution.

At END, the stack MUST contain exactly one value. That value is the output of the function.

A function that underflows the stack; executes an invalid operation; reaches the declared function boundary without END; contains an invalid operand; or terminates with anything other than exactly one stack value MUST be considered invalid.

4.11.1. Numerical Evaluation

GCMF v1 mathematical evaluation MUST use exact integer arithmetic unless a specific operation is explicitly defined to use another numerical domain.

An operation whose mathematical result is undefined within the applicable numerical domain MUST cause decoding to fail. Examples include division by zero, logarithms outside their valid domain, square roots of invalid values, and other undefined operations.

A decoder MUST reject a representation if evaluation produces a value that cannot be represented by the numerical domain defined for the representation.

Implementations MUST NOT silently round, truncate, saturate, wrap, or otherwise alter a mathematical result unless such behavior is explicitly defined by the applicable GCMF version.

All conforming implementations of the same GCMF version MUST produce the same mathematical result for the same valid input.

4.12. Example Custom Function

The function f(x) = 3x + 10 can be represented as:

CONST 3 X MUL CONST 10 ADD END

The logical execution is:

CONST 3   -> [3]
X         -> [3, x]
MUL       -> [3x]
CONST 10  -> [3x, 10]
ADD       -> [3x + 10]
END       -> result

4.13. X_start and X_end

For all non-LITERAL representations, the domain is specified using two unsigned GCMF-VLI fields:

+----------------+
| X_START        | GCMF-VLI
+----------------+
| X_END          | GCMF-VLI
+----------------+

X_start and X_end MUST be non-negative integers. The default domain is the integer sequence:

X = X_start, X_start + 1, ..., X_end

The number of generated values is:

N = X_end - X_start + 1

X_end MUST be greater than or equal to X_start. A decoder MUST reject a representation whose domain would require an invalid, negative, or implementation-prohibited number of values.

The number of generated values MUST also be consistent with the number of source values represented by the GCMF stream.

4.14. Base Encoding

The BASE field specifies the numerical radix associated with the domain representation. BASE is encoded as an unsigned GCMF-VLI integer. The base MUST be greater than or equal to 2.

A conforming implementation SHOULD support at least bases 2 through 36.

The BASE field does not alter the binary encoding of GCMF-VLI values, function opcodes, function bytecode, or other binary fields.

4.15. Base Interpretation

BASE specifies the radix used for the interpretation of X_start and X_end when a representation requires base-dependent numerical interpretation.

The mathematical values represented by X_start and X_end are independent of the selected radix. For example, a domain value of decimal 16 has the same mathematical value regardless of whether BASE is 10 or 16.

BASE therefore MUST NOT change the numerical value of X_start or X_end.

An encoder MAY evaluate multiple BASE values when selecting a representation if the selected base affects the representation length of the domain under the encoding rules defined by this specification.

If BASE does not affect the encoded length or interpretation of a candidate, changing BASE MUST NOT be used as a basis for selecting that candidate.

4.16. Residual Representation

If the Residual Flag is 1, a residual representation follows the primary function representation. The residual represents the difference between the original datum and the primary mathematical output. For every value:

r(i) = d(i) - f(x(i))

The original datum is reconstructed using:

d(i) = f(x(i)) + r(i)

The residual representation MUST itself be encoded using a valid GCMF function representation. Therefore a residual MAY be a predefined function or a custom function, subject to the restrictions imposed by this version of GCMF (see Section 4.17, which prohibits a residual from itself carrying a further nested residual).

The residual representation does not independently require a second Function Address byte; it uses the four-bit Residual Function Type defined in Section 4.17 instead.

4.17. Residual Function Container

When R = 1, the residual representation immediately follows the complete primary mathematical representation. The residual section is encoded as:

+----------------------------------------------------------+
| Residual Function Type | 4 bits                          |
+----------------------------------------------------------+
| Residual Function Data | variable, mandatory -- see below |
+----------------------------------------------------------+

The Residual Function Type uses the same function-type address table as the primary function (Table 1), excluding the residual flag. The residual function therefore contains exactly four function-type bits, and Residual Function Data is always present: a custom residual's data is its Function Length and Function Bytecode, and a predefined residual's data is its parameter fields, which may be zero-length for the parameterless functions of Section 4.9.1 but the field itself is never omitted outright.

For a custom residual, 0000 is used as the Residual Function Type. A custom residual MUST contain its Function Length followed by its Function Bytecode according to the CUSTOM function encoding rules.

A predefined residual MUST contain the parameter fields specified for its function type.

The Residual Function Type MUST NOT encode LITERAL (0001): a residual is always a mathematical representation, never a literal payload.

The residual function MUST NOT contain a residual flag and MUST NOT contain another residual representation. Recursive residual nesting is therefore prohibited in GCMF v1.

The residual representation MUST generate exactly the same number of values as the primary representation.

4.18. Literal

The LITERAL function has Function Type Address:

0001

and MUST NOT have the Residual Flag set. Its complete Function Address is therefore:

00001

LITERAL is a terminal representation. Immediately following the Function Address, the decoder MUST consume three zero-valued padding bits. These three padding bits align the stream to the next byte boundary. The remainder of the GCMF stream is then interpreted as raw source bytes.

+--------------------------+
| Magic                    |
+--------------------------+
| Version                  |
+--------------------------+
| Function Address         |
+--------------------------+
| Zero padding (3 bits)    |
+--------------------------+
| Raw source bytes         |
+--------------------------+
| Physical EOF             |
+--------------------------+

No function length is stored. No X_start is stored. No X_end is stored. No BASE field is stored. No residual representation is stored. There is no trailing Magic field or in-band EOF field; per Section 4.19, the physical end of the stream is the only termination condition.

The decoder MUST copy the literal payload directly to the output without interpretation or transformation.

4.19. Physical End Of File

The physical end of the GCMF file is the termination condition for the final field. No EOF byte or other in-band EOF marker is defined by GCMF, and the Magic field defined in Section 4.2 is never repeated within a representation.

This is particularly important for LITERAL, because every byte value from 0x00 through 0xFF is valid source data. Consequently, no byte value MAY be reserved as an EOF marker.

For LITERAL, EOF is the physical end of the GCMF stream. The final byte of the file is therefore the final literal source byte.

A transport or container system embedding GCMF MUST preserve the exact file length.

4.20. Complete Canonical Layout

This section restates, side by side and for reference only, the three mutually exclusive field sequences already given in full and without ambiguity in Section 4.8 (CUSTOM), Section 4.9 (PREDEFINED), and Section 4.18 (LITERAL). A single GCMF representation always matches exactly one of these three sequences; the bracketed items below are conditional exactly as specified in the section cited, not independently optional.

CUSTOM mathematical representation (Section 4.8):

GCMF
VERSION
FUNCTION ADDRESS
FUNCTION LENGTH
FUNCTION BYTECODE
X_START
X_END
BASE
[RESIDUAL FUNCTION TYPE, RESIDUAL FUNCTION DATA]   -- iff R = 1
EOF

PREDEFINED mathematical representation (Section 4.9):

GCMF
VERSION
FUNCTION ADDRESS
[FUNCTION PARAMETERS]   -- zero-length for the parameterless
                           functions listed in Section 4.9.1
X_START
X_END
BASE
[RESIDUAL FUNCTION TYPE, RESIDUAL FUNCTION DATA]   -- iff R = 1
EOF

LITERAL representation (Section 4.18):

GCMF
VERSION
00001
ZERO PADDING (3 BITS)
RAW DATA
EOF

4.21. Encoding Example

Consider the sequence:

10, 13, 16, 19, 22, 25

It can be represented by the linear function f(x) = 3x + 10 over the domain X = 0, 1, 2, 3, 4, 5. This is a PREDEFINED representation (LINEAR), so it follows the PREDEFINED field sequence of Section 4.9 with Function Parameters = (a=3, b=10) and no residual. The logical GCMF representation is therefore:

MAGIC
VERSION
FUNCTION ADDRESS = LINEAR, R = 0
a = 3
b = 10
X_START = 0
X_END = 5
BASE
PHYSICAL EOF

The decoder evaluates:

f(0) = 10
f(1) = 13
f(2) = 16
f(3) = 19
f(4) = 22
f(5) = 25

The resulting sequence exactly reproduces the source sequence.

4.22. Encoder Selection Algorithm

The encoder SHOULD construct multiple candidate representations. Candidates MAY differ in function type, function parameters, custom bytecode, domain, numerical base, or residual representation.

For every candidate C, the encoder computes L(C), the total encoded length in bytes. The encoder selects:

C* = arg min L(C)

The encoder MUST include all structural overhead in this calculation. Therefore the cost of a candidate includes magic, version, function address, function length where applicable, function bytecode, parameters, domain, base, residual data, and any required alignment.

The encoder MUST NOT select a mathematical representation merely because the function itself is shorter.

4.23. Literal Selection

The encoder MUST be permitted to select LITERAL when no mathematical representation provides sufficient compression.

The encoder SHOULD compare the best mathematical candidate against the LITERAL representation:

arg min (L(C_best_math), L(C_literal))

This prevents the creation of deliberately inflated mathematical representations for incompressible data.

4.24. Decoder State Machine

A conforming decoder can conceptually operate as follows:

START
  |
  v
READ MAGIC
  |
  v
READ VERSION
  |
  v
READ FUNCTION ADDRESS
  |
  +-----> LITERAL --> SKIP 3 PADDING BITS --> COPY REMAINDER --> END
  |
  v
[not LITERAL]
  |
  v
READ FUNCTION (CUSTOM: length + bytecode; PREDEFINED: parameters)
  |
  v
READ X_start
  |
  v
READ X_end
  |
  v
READ BASE
  |
  +-----> R = 0 -----> EVALUATE -----> END
  |
  +-----> R = 1 -----> READ RESIDUAL
                          |
                          v
                     EVALUATE RESIDUAL
                          |
                          v
                     RECONSTRUCT
                          |
                          v
                         END

4.25. Decoder Validation

A decoder MUST reject a GCMF stream if any of the following occurs:

  • The magic number is invalid.
  • The version is unsupported.
  • The Function Address is invalid, including LITERAL with the residual flag set (Section 4.4.2).
  • A required VLI is truncated.
  • A VLI is malformed.
  • A custom function exceeds its declared length.
  • A custom function lacks a valid END.
  • A function causes stack underflow.
  • A function terminates with an invalid stack state.
  • X_end is less than X_start.
  • BASE is less than 2.
  • A required function parameter is missing.
  • A residual representation is malformed, including a Residual Function Type of LITERAL (Section 4.17).
  • A prohibited recursive residual is encountered.
  • The mathematical evaluation produces a value that cannot be represented by the selected numerical representation.
  • The stream terminates before all mandatory fields are read.

A decoder SHOULD also impose implementation-defined limits on:

  • maximum function length;
  • maximum domain size;
  • maximum stack depth;
  • maximum numerical magnitude;
  • maximum execution time.

Such limits are important because GCMF functions are executable mathematical expressions and should not be permitted to consume unbounded computational resources.

4.26. Canonical Encoding

A GCMF encoder SHOULD produce canonical encodings. A canonical representation MUST:

  • use the shortest valid GCMF-VLI representation;
  • avoid unnecessary leading VLI groups;
  • use the minimum required function length;
  • terminate bytecode with exactly one END;
  • avoid unnecessary residual representations;
  • avoid unnecessary domain extension;
  • avoid unnecessary padding;
  • select the smallest valid complete representation when deterministic encoding is required.

Canonicalization permits byte-for-byte comparison of equivalent GCMF representations.

4.27. Versioning

The version byte identifies the binary interpretation rules. A future version MAY:

  • add predefined functions;
  • add bytecode instructions;
  • modify residual semantics;
  • add new representation modes;
  • define previously reserved fields.

Existing function addresses MUST NOT be silently reassigned within a compatible version. A new incompatible interpretation MUST use a new version number.

4.28. Reserved Space

The initial GCMF function address space has no unused base-function address because all 16 four-bit values are assigned. Future extensions SHOULD therefore use one of the following mechanisms:

  • a new GCMF version;
  • extension instructions;
  • additional extension containers;
  • a future extension mechanism explicitly defined by the specification.

The five-bit address space itself MUST NOT be silently expanded within GCMF v1. The bytecode instruction space is similarly fully allocated.

4.29. Losslessness Requirement

For every valid GCMF representation G, decoding MUST satisfy:

Decode(G) = D

where D is the exact original input byte sequence. For mathematical representations:

d(i) = f(x(i)) + r(x(i))

For exact mathematical representations, r(x(i)) = 0. For LITERAL:

Decode(G) = LiteralPayload(G)

No rounding, approximation, or numerical loss is permitted unless explicitly introduced by a future GCMF version.

4.30. Summary of Binary Grammar

The logical grammar of GCMF v1 is:

GCMF_FILE :=
    MAGIC
    VERSION
    FUNCTION_ADDRESS
    REPRESENTATION

REPRESENTATION :=
      LITERAL_REPRESENTATION
    | MATHEMATICAL_REPRESENTATION

LITERAL_REPRESENTATION :=
    LITERAL_FUNCTION_ADDRESS
    ZERO_PADDING_3_BITS
    RAW_BYTES

MATHEMATICAL_REPRESENTATION :=
    FUNCTION
    X_START
    X_END
    BASE
    [RESIDUAL]

FUNCTION :=
      CUSTOM_FUNCTION
    | PREDEFINED_FUNCTION

CUSTOM_FUNCTION :=
    FUNCTION_LENGTH
    FUNCTION_BYTECODE

PREDEFINED_FUNCTION :=
    [FUNCTION_PARAMETERS]

RESIDUAL :=
    RESIDUAL_FUNCTION_TYPE
    RESIDUAL_FUNCTION_DATA

RESIDUAL_FUNCTION_DATA :=
      CUSTOM_RESIDUAL_DATA
    | PREDEFINED_RESIDUAL_DATA

CUSTOM_RESIDUAL_DATA :=
    FUNCTION_LENGTH
    FUNCTION_BYTECODE

PREDEFINED_RESIDUAL_DATA :=
    [FUNCTION_PARAMETERS]

PHYSICAL_EOF :=
    END_OF_PHYSICAL_GCMF_STREAM

The fundamental mathematical decoding equation is:

d(i) = f(x(i)) + r(x(i))

where r(x(i)) = 0 for representations without residuals. For LITERAL, Decode(G) = LiteralPayload(G). No additional EOF field is encoded.

5. IANA Considerations

This document defines a working, unregistered MIME type, application/gcmf, as described in Section 2. This document does not request any registration action from IANA at this time. Should GCMF advance toward broader adoption, a future document MAY request registration of application/gcmf in accordance with the procedures of [RFC2046] and BCP 13.

6. Security Considerations

GCMF CUSTOM function representations embed executable stack-based bytecode within the file format, as described in Section 4.10. A decoder that evaluates untrusted GCMF input therefore executes untrusted, attacker-supplied instructions. Implementations MUST treat GCMF decoding of CUSTOM and MODULAR functions as execution of untrusted code and SHOULD apply appropriate sandboxing.

Because GCMF functions are evaluated over a domain that can be specified independently of the resulting output size, a maliciously crafted file can specify an extremely large [X_start, X_end] domain, or a MODULAR or POLYNOMIAL function with a large nesting or degree, in order to force a decoder to perform an excessive amount of computation or produce an excessive volume of output from a very small input file. This is a form of decompression-bomb risk analogous to those found in other compression formats. Implementations SHOULD impose configurable limits on maximum domain size, maximum function length, maximum stack depth, maximum recursive MODULAR nesting depth, maximum numerical magnitude, and maximum decode execution time, as noted in Section 4.25.

Certain bytecode operations, such as DIV, MOD, LOG, LOG10, and SQRT, are undefined for some operand values (for example, division by zero or the logarithm of a non-positive number). Implementations MUST reject such evaluations rather than substituting an implementation-defined or platform-defined result, as required in Section 4.11.1, since inconsistent handling of undefined operations across implementations could otherwise be leveraged to produce divergent decoded output from the same input.

Because GCMF-VLI and the bit-packed Function Address are variable-width fields that need not be byte-aligned, a non-conforming or naive decoder implementation is at heightened risk of buffer over-read or integer overflow when parsing malformed or truncated input. Implementations MUST validate that sufficient input remains before consuming any field and MUST reject truncated streams as described in Section 4.25.

GCMF does not itself provide authentication, integrity protection, or confidentiality for encoded data. Applications that require these properties for GCMF streams transmitted or stored in untrusted environments SHOULD apply them at another layer.

7. Normative References

[RFC2046]
Freed, N. and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part Two: Media Types", RFC 2046, DOI 10.17487/RFC2046, , <https://www.rfc-editor.org/rfc/rfc2046>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.

8. Informative References

[J_RISSANEN_1978]
Rissanen, J., "Modeling by shortest data description", Automatica vol. 14, no. 5, pp. 465-471, .

Appendix A. Example GCMF Representation

This appendix reproduces, for reference, the worked example of Section 4.21 in a single consolidated view.

Given the source sequence 10, 13, 16, 19, 22, 25 (six 8-bit unsigned values, a 6-byte source), an encoder implementing this specification could produce a LINEAR representation with a = 3, b = 10, X_start = 0, X_end = 5, discovering that:

f(x) = 3x + 10

f(0) = 10
f(1) = 13
f(2) = 16
f(3) = 19
f(4) = 22
f(5) = 25

which exactly reproduces the six-value source sequence with an exact (residual-free) representation, per Section 3. Per Section 4.22, the encoder would compare the total encoded length of this LINEAR representation, including all structural overhead, against the LITERAL representation of the same six bytes, and select whichever candidate yields the smaller value of L(C).

Table 1: Function Type Addresses
AAAA Function Formula
0000 CUSTOM User-defined
0001 LITERAL N/A -- raw bytes, see Section 4.18
0010 CONSTANT F(x) = c
0011 LINEAR F(x) = ax + b
0100 ARITHMETIC F(x) = a + xd
0101 GEOMETRIC F(x) = a r^x
0110 POLYNOMIAL F(x) = sum_(i=0)^n a_i x^i
0111 EXPONENTIAL F(x) = a b^x
1000 LOGARITHMIC F(x) = a log_b(x) + c
1001 POWER F(x) = a x^b + c
1010 MODULAR F(x) = G(x) mod m
1011 FIBONACCI F(x)=F(x-1)+F(x-2), x>=2, F(0)=0, F(1)=1
1100 FACTORIAL F(x) = x!
1101 TRIANGULAR F(x) = x(x+1)/2
1110 SQUARE F(x) = x^2
1111 CUBE F(x) = x^3

NOTE: the LITERAL row was previously listed with the formula "F(x) = x", which incorrectly implied LITERAL evaluates a function. Per Section 4.18, LITERAL stores no function, domain, or base; the decoded output is the raw payload copied verbatim (Section 4.29).

Table 2: Function Bytecode Opcodes
OPCODE MNEMONIC STACK OPERATION
00000 CONST Push constant
00001 X Push current x
00010 ADD a + b
00011 SUB a - b
00100 MUL a * b
00101 DIV a / b
00110 MOD a mod b
00111 POW a ^ b
01000 NEG -a
01001 ABS |a|
01010 SQRT sqrt(a)
01011 LOG ln(a)
01100 LOG10 log10(a)
01101 EXP e^a
01110 SIN sin(a)
01111 COS cos(a)
10000 TAN tan(a)
10001 ASIN arcsin(a)
10010 ACOS arccos(a)
10011 ATAN arctan(a)
10100 FLOOR floor(a)
10101 CEIL ceil(a)
10110 ROUND round(a)
10111 MIN min(a, b)
11000 MAX max(a, b)
11001 AND a & b
11010 OR a | b
11011 XOR a xor b (bitwise)
11100 SHL a << b
11101 SHR a >> b
11110 DUP Duplicate top stack value
11111 END End function

Appendix B. Changes from draft-dutta-gcmf-00

This appendix is non-normative and summarizes the corrections made relative to draft-dutta-gcmf-00; it will be removed before this document advances.

Author's Address

Srijal Dutta
The ZSMC Co.
Gurugram
Haryana
India