path: root/html/notes/nan.md

# NaN-Packing

NaN-packing (also called NaN-boxing) is a strategy involving the use of NaN
bit patterns, that are otherwise unused, to store various values in them.

In the implementation of a dynamically typed language, this can be used to
ensure that all types in the language can be represented by a single 64-bit
value, which is either a valid double, an actual NaN value, or one of the
other NaN bit patterns that represent some other type, potentially in the
form of a pointer to a heap object containing further data.

This works because pointers only need 48 bits in practice, and the range of
unused NaN bit patterns contains an astounding `2^53 - 4` different values.

IMPORTANT NOTE: All illustrations of data structures and bit patterns use
big-endian.  When implementing the strategies described herein, it may be
necessary to reorder the elements.  For example, the elements of packed
structs in Zig are ordered least to most significant.


## The double format

The IEEE 754 double-precision binary floating-point aka binary64 format is:

    { sign: u1, exponent: u11, fraction: u52 }

Possible types of values a double can encode include:

    { sign == any, exponent != 0x7ff, fraction == any } :: Real (finite)
    { sign == any, exponent == 0x7ff, fraction == 0x0 } :: Infinity
    { sign == any, exponent == 0x7ff, fraction != 0x0 } :: NaN

Note:

    0x7ff = u11 with all bits set (0b11111111111)

In other words:

    all exponent bits set, fraction bits all zero :: Infinity
    all exponent bits set, fraction part non-zero :: NaN


## Details of NaN values

There are two different NaN types: signaling and quiet.  Quiet NaN may be
returned by FP operations to denote invalid results, whereas signaling NaN
are never returned by FP operations and serve other purposes.

Modern hardware sets the MSB of the fraction to indicate that the NaN is a
quiet one, so let's refine our definition for denoting NaN values:

    { sign: u1, exp: u11, quiet: u1, rest: u51 }

Variants of NaN:

    { sign == any, exp == 0x7ff, quiet == 0, rest >= 0x1 } :: sNaN
    { sign == any, exp == 0x7ff, quiet == 1, rest == any } :: qNaN

Note that in case of the signaling NaN, the rest of the fraction must be
non-zero, since otherwise the entire fraction part would be zero and thus
denote an infinity rather than a NaN.

Most systems have a "canonical" quiet NaN that they use:

    { sign == any, exp == 0x7ff, quiet == 1, rest == 0x0 } :: cqNaN

The sign bit of the canonical quiet NaN is undefined and may differ from
operation to operation or depending on the platform.

It's useful to see a few common examples expressed in hex:

    0x7ff8000000000000 :: cqNaN, sign bit nil
    0xfff8000000000000 :: cqNaN, sign bit set

    0x7ff8000000000001 :: smallest non-canon qNaN, sign bit nil
    0xfff8000000000001 :: smallest non-canon qNaN, sign bit set

    0x7fffffffffffffff :: largest non-canon qNaN, sign bit nil
    0xffffffffffffffff :: largest non-canon qNaN, sign bit set

    0x7ff0000000000001 :: smallest sNaN, sign bit nil
    0xfff0000000000001 :: smallest sNaN, sign bit set

    0x7ff7ffffffffffff :: largest sNaN, sign bit nil
    0xfff7ffffffffffff :: largest sNaN, sign bit set


## Unused NaN bit patterns

Let's start with the quiet NaN values.

Theoretically, there only needs to be one canonical quiet NaN, so we would
have `2^52 - 1` unused bit patterns in the quiet NaN range.  In practice,
however, the sign bit may differ from one operation to the next.

For example, the fabs function may simply clear the sign of the argument,
without minding it being a NaN.  In that case, if the platform's regular
canonical NaN is the one with the sign bit set, we would end up getting
another, "semi-canonical" quiet NaN bit pattern, with the sign bit nil.

So, both variants of the canonical quiet NaN are in use.

This leaves `2^52 - 2` definitely-unused quiet NaN bit patterns:

    { sign == any, exp == 0x7ff, quiet == 1, rest >= 0x1 } :: Unused qNaN

Remember that signaling NaN are defined in a very similar way:

    { sign == any, exp == 0x7ff, quiet == 0, rest >= 0x1 } :: sNaN

Since none of those can be returned by FP operations, they could all be seen
as unused, giving us another `2^52 - 2` bit patterns.

In total, this gives us `2^53 - 4` definitely-unused NaN bit patterns.


## Representing Zisp values and pointers as unused NaN bit patterns

Zisp wants to store two different things in unused NaN patterns:

1. Pointers (to anything in principle)

2. Non-double primitive aka "immediate" values

It may seem intuitive to use signaling NaN for one, and quiet NaN for the
other.  However, this would fragment our "payload" bits, since we would be
using the sign bit as its MSB and the remaining 51 bits of the fraction as
the rest of the payload.

Further, we want to use as many bit patterns as possible for fixnums, so we
can have a nice large fixnum range.  To this end, it would be nice if we
could, for example, use all bit patterns where the sign bit is set for our
representation of fixnums, and then the range of bit patterns with the sign
bit unset can be shared among the remaining values, and pointers.

Then let's do exactly that, and use the sign as the first major distinction
between fixnums and other values, using it as a sort of `is_int` flag:

    { sign == 0x0, exp == 0x7ff, payload == ??? } :: Non-Fixnum
    { sign == 0x1, exp == 0x7ff, payload == ??? } :: Fixnum

It will become apparent in a moment why we haven't defined the payload yet.

Given that our payload is the entire fraction part of the IEEE 754 double
format, we must be careful not to use the following two payload values
regardless of the sign bit:

1. Zero: This would make the bit pattern represent an infinity, since the
payload is the entire fraction and a zero fraction indicates infinity.

2. `0x8000000000000` (aka only the MSB is set): This would make the bit
pattern a canonical quiet NaN, since the payload MSB is the quiet bit.

This means that in each category (sign bit set, or nil) we have `2^52 - 2`
possible bit patterns, and the payload has a rather strange definition:

    0x0 < payload < 0x8000000000000 < payload < 0xfffffffffffff

Can we really fit a continuous range of fixnum values into that payload
without significantly complicating things?  Yes, we can!  Observe.


## Fixnum representation

We will store positive and negative fixnums as separate value ranges, using
the quiet bit to differentiate between them.

Let's go back to considering the quiet bit a separate field:

    { sign == 0x1, exp == 0x7ff, quiet == 0x0, rest >= 0x1 } :: Positive
    { sign == 0x1, exp == 0x7ff, quiet == 0x1, rest >= 0x1 } :: Negative

But, I hear you say, the positive range is missing zero!  Worry not, for
maths is wizardry.  We will actually store positive values as their ones'
complement (bitwise NOT) meaning that all bits being set is our zero, and
only the LSB being set is the highest possible value.

This must be combined with a bitwise OR mask, to ensure that the 13 highest
of the 64 bits turn into the correct starting bit pattern for a signed NaN.
Unpacking it is just as simple: Take the ones' complement (bitwise NOT) and
then use an AND mask to unset the 13 highest:

    POS_INT_PACK(x)   = ~x | 0xfff8000000000000

    POS_INT_UNPACK(x) = ~x & 0x0007ffffffffffff

If you've been paying very close attention, you may notice something: Given
that we know the 13 highest bits must always have a certain respective value
in the packed and unpacked representation (12 highest set when packed, none
set when unpacked), we can use an XOR to flip between the two, and the same
XOR can take care of flipping the remaining 51 bits at the same time!

This also means packing and unpacking is the same operation:

    POS_INT_PACK(x)   = x ^ 0xfff7ffffffffffff

    POS_INT_UNPACK(x) = x ^ 0xfff7ffffffffffff

There we go; packing and unpacking 51-bit positive fixnums with one XOR!
Amazing, isn't it?

As for the negative values, it's even simpler.  This time, the correct NaN
starting pattern has all 13 bits set, since the quiet bit being set is what
we use to determine the number being negative.  And would you believe it;
this means the packed negative fixnum already represents itself!

    NEG_INT_PACK(x)   = x

    NEG_INT_UNPACK(x) = x

Isn't that unbelievable?  I need to verify this strategy further, but based
on all information I can find about NaN values, it should work just fine.

The only disappointing thing is that it's positive integers that need an XOR
to pack and unpack, rather than negative ones.  One would expect positive
values to occur much more frequently in typical code.  But I think we can
live with a single XOR instruction!


## Pointers & Others

We still want to represent the following, which must share space within the
`2^52 - 2` bit patterns that can be packed into an unsigned NaN:

- Pointers of various kinds
- Unicode code points (21-bit values)
- False, true, null, end-of-file, and maybe a few more singletons

It seems sensible to split this into two main categories: pointers and other
values.  Let's use the quiet bit as a `pointer` flag:

    { sign == 0x0, exp == 0x7ff, quiet == 0x0, rest >= 0x1 } :: Other
    { sign == 0x0, exp == 0x7ff, quiet == 0x1, rest >= 0x1 } :: Pointer

Note how neither type is allowed to have a zero payload, since in case of an
unset quiet bit, this would make our value an infinity, and in case of a set
quiet bit it would give us a canonical quiet NaN.  Each of them is allowed
any other payload than zero.


## Pointers

It would seem that we have 51 bits left to represent a pointer (though we
need to avoid the value zero).  But we only need 48 bits... or even less!
Since allocations happen at 8-byte boundaries on 64-bit machines, we only
really need 45 of the 48 bits, given the least significant 3 will never be
set.  This gives us a whole 6 free bits to tag pointers with!  If we have
that much play room, we can do some crazy things.

### Foreign pointers

Firstly, let's introduce the concept of a "foreign" pointer.  This means the
pointer doesn't necessarily point to a Zisp object, and may not be 8-byte
aligned.  As it may point to anything, there's no point in defining further
bits as tagging additional information, so we have all 50 bits available.

Let's cut out the 12 high bits of our double since we already know what they
must contain, and look at the definition of our 52-bit payload.

I will also mix up the notation a bit, to indicate that some fields are only
defined if a previous field has a given value.

    { pointer == 0x1, foreign: u1, rest: u50 }

(The `pointer` field is the `quiet` bit i.e. MSB of the 52-bit fraction.)

If the foreign bit is set, then the entire `rest` field shall be seen as
opaque and may contain any value.  Another way to look at this is that we
essentially defined another fixnum range of 50 bits.  This can include the
value zero, since the foreign bit being set ensures we don't step on the
forbidden all-zero payload value.

### Zisp pointers

Now let's look at what we can do with "native" Zisp pointers.

Wouldn't it be nice if our language had an explicit "pointer" data type and
it didn't require any additional heap allocation?  So let's decide that one
bit is dedicated to distinguishing between an explicit pointer object, and
regular pointers that stand in for the object being pointed to.

Perhaps it would be good to show some Zisp pseudo-code to explain what that
means, since it may be a strange concept:

    ;; In memory, vec is represented as a regular/direct vector pointer.
    (define vec (vector 1 2 3))

    ;; We can of course use this variable as a vector.
    (vector? vec)      ;=> #t
    (vector-ref vec 0) ;=> 1

    ;; Now we create an explicit pointer object pointing to that vector.
    ;; Distinguished by a special bit in the in-memory value of vec-ptr.
    (define vec-ptr (pointer vec))

    ;; This variable is *not* a vector; it's a vector-pointer.
    (vector? vec-ptr)      ;=> #f
    (vector-ref vec-ptr 0) ;ERROR
    (pointer? vec-ptr)     ;=> #t
    (pointer-ref vec-ptr)  ;=> #(1 2 3)

This is *not* the same thing as a box, because it can *only* refer to heap
allocated objects, not immediates, whereas a box would be able to hold an
immediate value like an integer or double as well.

    (pointer 42) ;ERROR
    (box 42)     ;=> #<box:42>

A box would necessarily need heap allocation, whereas a pointer doesn't.

It's *also not* the same thing as a foreign pointer, because those can be
anything, whereas these pointer objects definitely point to Zisp objects.

Pointers may or may not be mutable; I've not made up my mind yet.  It may
seem like a pointless data type, but it adds a little bit of expressive
strength to our language.  For example, when working with an FFI.  And
there's really not much else we can do with all our bits.

Let's use the term "indirect" for this tag, since "pointer" is already used:

    { pointer == 0x1, foreign == 0x0, indirect: u1, rest: u49 }

Should these indirect pointers objects be mutable, then they may contain a
null pointer; the forbidden zero value is avoided through the fact that the
indirect bit is set.

Hmm, indirect pointers may instead become weak pointers at some point!  This
would fit perfectly since they can contain null.

Direct or indirect makes no difference to the fact that the pointer value
will be 8-byte aligned, so we still have 4 bits for more information about
what's being pointed to.  Also, since the actual pointer value can never be
zero (all non-foreign pointers must point to a valid Zisp object), we avoid
the forbidden zero pattern.  Thus, we can indicate 16 different values with
our 4 remaining bits.

It would have been nice to avoid fragmentation of these remaining tag bits.
However, we want to avoid shifting, so let's go with this definition for the
remaining 49 bits:

    { tag_high: u1, pointer_value: u45, tag_low: u3 }

The pointer value is extracted by masking the entire bit sequence, so it
actually becomes a 48-bit value without further shifting.

(This part of the article is kinda obsolete.  Implementation details are up
for debate and we may or may not use bit shifting.  It's not that expensive
of an operation, after all.)

The tag can be used to tell us what we're pointing to, so that type checks
often don't require following the pointer.  The memory location that's being
pointed to may duplicate this information, since we may want to ensure that
any Zisp object on the heap carries its type information within itself, but
I'm not yet decided on that.

In any case, let's list some common heap data types that our 4-bit tag can
represent, making sure to have an "other" wildcard for future extensions.

The right side shows the value of the type tag when it's acquired by masking
the 49-bit Zisp pointer payload.

    0. String (Symbol) ... 0x0000000000000
    1. Pair (List)         0x0000000000001
    2. Vector ............ 0x0000000000002
    3. Map (Hash-table)    0x0000000000003
    4. Box ............... 0x0000000000004
    5. Record              0x0000000000005
    6. Class ............. 0x0000000000006
    7. Instance            0x0000000000007
    8. Text .............. 0x1000000000000
    9. Byte-vector         0x1000000000001
    10. Procedure ........ 0x1000000000002
    11. Continuation       0x1000000000003
    12. Port ............. 0x1000000000004
    13. Error              0x1000000000005
    14. Enum ............. 0x1000000000006
    15. Other              0x1000000000007

This list is likely to change; for example: errors should probably be class
instances, continuations could be merged with procedures, and so on.  But
this gives us a rough picture and demonstrates that 16 distinct values is
quite sufficient for avoiding a pointer de-reference in type checking.

(Why is it so important to avoid following a pointer when checking a type?
Who knows?  Did I say it was important?  Why look at me like that??)

(Since I wrote this, I decided to use bit shifting after all, and the tags
are straightforward values from 0 to 15.)


## Other values

We still have one entire `2^51 - 1` value range left.  We will split it the
following way.  This one uses a very simple partitioning scheme:

    { tag: u3, payload: u48 }

The following tags are defined:

    001 = short string
    010 = char (Unicode code point)
    100 = singletons (false, true, etc.)

Other tags are undefined and reserved for the future.  Note that 000 is
missing, so we automatically avoid the forbidden zero payload.

### What the heck is a "short string"?

Remember that [strings are immutable](symbols.html) in Zisp.  This allows us
to use an amazing optimization where short strings can be represented as
immediate values.

We can't get to 56 bits (7 bytes), but 48 bits (6 bytes) fits perfectly into
our payload!  So any interned string (equivalent to a Scheme symbol) in Zisp
will in fact be an immediate value if 6 bytes or shorter, and doesn't need
any heap allocation.  Awesome!

There can still be uninterned strings that are 6 bytes or shorter, and
calling intern on them would return the canonical, immediate version.

### Unicode code points

This is an easy one.  We have 48 bits, and only need 21.  Just write the
Unicode code point into the payload: done.

This value range may be split in the future to fit other things in it, as
we've wasted a ton of bits here.

### Singletons

This 48-bit value range contains various singletons like Boolean values, the
empty list aka null, and so on.

This is even more wasteful than using 48 bits for Unicode, so again this
value range may be partitioned further at some point.

### Undefined ranges

We have a whole 48-bit value range (sans one forbidden value) that's still
unused, plus another 50-bit range (or two 49-bit ranges, or three 48-bit).

It's incredible just how much stuff you can cram into a NaN.  I would have
never thought it possible.

Ours may just be the most sophisticated NaN-packing strategy ever devised,
because I couldn't find any information on the web about the possibility of
using both signaling and quiet NaNs.  All articles I've stumbled upon either
claim that you must avoid signaling NaNs or quiet NaNs, or they take a naive
approach to the subdivision of the available bit patterns and end up wasting
tons of bit real estate.

Stay tuned for the development of Zisp, because this is getting serious!

<!--
;; Local Variables:
;; fill-column: 77
;; End:
-->