Subject: [Cbor] Unsigned and negative

From: Carsten Bormann <[email-masked]>
Date: Tue, 8 Sep 2020 18:44:40 +0200

I see that we have several IESG comments that question the “unsigned or negative” language that we are using for describing integers in ℤ.

Most people are brought up with a trinity of positive, zero, and negative integers, as this has a certain symmetry.
In the math world, there is some confusion about “natural numbers”, which are sometimes the set of positive integers (ℕ₁), sometimes the set of non-negative integers (ℕ₀, which we call “unsigned” in CBOR).

In programming languages, integer numbers (ℤ restricted to some range) have been available since the 1950s.  When it became obvious that ℕ₀ was another interesting range as it could support twice as many positive numbers and machine-supported modulo arithmetic, it was much harder to agree on a name.  “Natural" was ambiguous.  Some 1970s languages (notably Modula-2) adopted “Cardinal".  But these did not stick.  What did stick was “unsigned”, as introduced into the C language in the late 1970s.  Initially, this was intended as an attribute that could be added to a type name such as int or long, but the type name could be left off (defaulting to int), and thus “unsigned” became the name for ℕ₀ in many environments.

CBOR has non-negative and negative numbers, separated into two major types (“unsigned” and “negative”) so it is easier to support unsigned numbers, which are rather important in constrained environments.  Instead of creating overlapping types with “unsigned” and “signed”, CBOR opted for a separate “negative” type, inspired by protobuf’s slightly weird integer encoding.  Protobuf puts the sign into the LSB and shifts the integer one to the left (“ZigZag encoding”), which is relatively expensive to do.  CBOR instead encodes the sign bit into the major type, so that the combination of unsigned and negative integers creates 9-, 17-, 33-, and 65-bit representations of signed integers (which does cause a little cognitive dissonance for advocates of two’s complement signed representations, but avoids having to encode the representation data type for numbers that could be represented in both unsigned and signed platform types).

So when we talk about ℕ₀, we don’t have to use the clumsy “non-negative”, we can just say “unsigned" (the name we gave to major type 0).  With major type 1, the sign is implied negative, so we just call it “negative”.  The symmetry is the line between 0 (0x00 in CBOR) and -1 (0x20 in CBOR); there is no zero in the “negative” ranges (as it should not be if the name is taken for face value).

I propose we continue to use this clean terminology — we can still say “positive integer” if we really want to restrict something to ℕ₁, but the CBOR types for integers are “unsigned” (mt=0, ℕ₀) and “negative” (mt=1, ℤ \ ℕ₀).  Tag 2/3 continue exactly this split for more than 64-bit (65-bit if you think signed) integers.

Grüße, Carsten