I Accidentally Invent a New, Worse kind of Endianness

Recommended reading: Ternary, Septivigntimal

So, I was writing an implementation of Ternary RAM when I encountered a problem.

I used a completely reasonable representation for ternary pages,

struct TernaryPage([Ternary<27>; PAGE_SIZE]);

but ran into a subtle bug.

You see, using balanced ternary, everything is centered around 0. This means the address range for each page is not measured from $$0\dots2^n-1$$ but is instead measured as $$-\lfloor {3^n}/{2} \rfloor \dots \lfloor {3^n}/{2} \rfloor$$

This really isn't a problem, it's akin to a shift in frame of reference in physics. It's helpful to solve this specific problem at hand, but isn't fundamentally different. That being said, like a change of reference, it can lead to some strange new things to deal with.

To understand the next part, I recommend you read my more in-depth posts on ternary computing, but I'll give a quick overview for now.

Balanced Ternary

Binary uses 2 digits, usually 1 and 0. Ternary uses 3 digits. You can pick the digits -1, 0, and 1, giving you a very nice way of representing negative numbers. You simply multiply the digit by the usual power of 3 and add it to the result, just like any other base system, we do here, using T to represent -1 for convenience:

                        ┌──┬─┬─┬─┬─┐              
                    num:│1 │T│0│T│1│              
                        └──┴─┴─┴─┴─┘              
    digit position (n):  5  4 2 1 0               
value multiplier (3^n): 81 27 9 3 1                                 

Not too complicated. But this does mean that the representable numbers for $n$ ternary digits grows radially from 0.

  Digits: 2
  Grows in Both Directions
             │  
 ┌───────────▼───────────┐  
 ▼                       ▼
-4 -3 -2 -1  0  1  2  3  4
TT T0 T1 0T 00 01 1T 10 11

This also isn't too hard to deal with when doing math, since it's not fundamentally different from the way other ternary systems work¹.

Balanced Ternary in Computers

But when doing my virtual machine, I made a decision to support 2 types of numbers:

// [`Ternary<SIZE>`] represented using `(u32, u32)`
type Word = Ternary<27>;
type Tryte = Ternary<9>;

Since they're both represented using (u32, u32), representing memory using

struct TernaryPage([Tryte; PAGE_SIZE_TRYTES]);

would be 3x as inefficient, a waste of memory that's completely unnecessary, and absolutely terrible for cache locality.

So I opted for using Word instead. A reasonable choice. I had already decided on using little-endian representation for nesting Trytes in Words, since that's most natural to me. So, let's grab the Word at index 0.

fn index_word(&self, index: Ternary<PAGE_INDEX_SIZE>) -> Word {
    // Convert into `isize`
    let index: isize = index.try_into().unwrap();
    // Add $floor(3^n / 2)$ to bias the bottom index (all -1s) to 0,
    // for binary indexing
    let index: usize = (index + (3isize.pow(PAGE_INDEX_SIZE) / 2)) as usize;
    // Maintain natural alignment. I'm sure this won't cause problems later!
    assert_eq!(index % 3, 0);
    self.0[index]
}

Not too complicated, right? Now consider this: if we assume the tryte at index 0 is also the first tryte in the word at index 0, (which we know because early on in design, I opted for little-endian), what does our address range look like?

Consider this brief example where we use 2 ternary digits to index a page. This means 3 words and 9 trytes, since there are 9 distinct representations with $n=2$

┌─────────┬─────────┬─────────┐
│  Word   │  Word   │  Word   │
└─────────┴─────────┴─────────┘
 -3 -2 -1  0  1  2   3  4  5  
 ▲                         ▲ 
 │                         │ 
 Lowest tryte   Highest tryte 
 index is -3    index is... 5?

Uh oh. I thought these were supposed to grow radially from 0?

Well, if ranges naturally radiate from zero, wouldn't a pointer to a word point to... the middle? That way, larger values grow surrounding the address. This would fix the problem, and now our diagram looks like this:

┌─────────┬─────────┬─────────┐
│  Word   │  Word   │  Word   │
└─────────┴─────────┴─────────┘
 -4 -3 -2  -1  0  1   2  3  4  
               ▲ 
               │

There we go! We don't have to change our indexing function at all! We would just need to write our index_tryte function very carefully.

But this is not the system that I originally went out to design. We don't really have a defined "start" of our number anymore, unlike what is clearly the start in binary. We can still use endianness as a way of specifying whether data starts at larger or smaller addresses, but it no longer lines up with how pointers to values are represented. But that isn't endianness! It's a new thing. Imagine if we started representing pointers as pointing to the sizeof(type) / 2th byte! This is absurd in binary, but we're now confronted with the fact that it makes a lot of sense in ternary. Oh dear.

This means we are faced now with 2 separate details of memory representation: endianness and ...pointedness? Pointer alignment? But this does give a solution: we can simply use little-??? as our pointer representation. This means an aligned pointer to a word must be aligned to $i \mod 3 \equiv [T]$ or in pseudocode, addr % 3 == -1.

This solves the problem. Our new, final diagram looks like this:

┌─────────┬─────────┬─────────┐
│  Word   │  Word   │  Word   │
└─────────┴─────────┴─────────┘
 -4 -3 -2  -1  0  1   2  3  4  
            ▲ 
            │

This means the range can be represented radially from 0, but pointers point to the beginning of a word. This is a little gross, but maybe necessary for balanced ternary computing. It's at least the solution I'll be using for my VM. Someone smarter than me may be able to come up with something better.

A Generalization

We haven't come up with a term for this yet, because in binary this is absurd to even consider². We always point to the lowest byte of the range of memory, and deal with endianness separately. It just so happens that the natural "first" tryte is in the middle of a larger value now, and we must deal with this fact in a practical sense.

This means coining a term which can encompass all 3 rational variants: pointer points at the lowest address, the middle address, and the highest address. I thought it over, and came up with a few options, but I think byteedness/tryteedness makes the most sense. This would be pointing at the middle would be middle trytedness, pointing at the least address would be little-trytedness, and pointing at the highest would be big-trytedness. This lines up with endianness, so should be familiar and about as easily explainable. That being said, I foresee this being similarly painful to deal with. If anybody thinks of something better though, let me know!

Lessons

It's very interesting how speed gains from alignment naturally occur here. I always find it interesting when the architecture for emulating systems lines up with how physical systems behave.