000. Background

In 1959, N.P. Brusentsov developed a unique Setun computer for MSU. It was based on the ternary number system, and although the element base was partially binary, which resulted in cost overruns, the machine proved to be economical and reliable. Today, the ternary car can be seen except in the museum, the binary code won.

But, as I said earlier , there will always be people ready to save the technologies of the past in the form of emulators.

00+. Theoretical basis

This article discusses the ternary symmetric number system. The numbers in it are positive and negative, that is, -1/0/1 or more generally accepted - / 0 / +. From this property follows native support by our future computer of negative numbers.

There are a couple of arguments in defense of the ternary number system and the ternary logic. The cost-effectiveness of data storage for each discharge is obvious, saving lines in the tires, a large capacity of the usual data types.
')


There is a formula y = ln (x) / x, the physical meaning of which I understand as "the ratio of the volume of stored information to the complexity of its storage," where complexity increases along the X axis.

The main disadvantage is the absence of a base element, which is able to be in three states and at the same time work effectively in modes suitable for building processors. But for the emulator this is not a problem. Moreover, the schemes of the composite ternary elements are known. If we estimate how many transistors in modern processors are really responsible for the instruction set, and how much for optimization, it turns out that the implementation of the triple processor itself is not such a problem.

0 + -. Prerequisites

I learned about the work of N. P. Brusentsov relatively recently. Having studied some materials on Setun, I realized that there is no need to go all the way over and you can use the knowledge of our days. As far as I know, the ternary virtual machine was also developed at MSU. But there are few materials on it, but there are no source codes at all.

Just at this moment N. Wirth published the first works of the Oberon 2013 project.



Own command system RISC-like processor, simple language and simple compiler for him prompted me to the idea that it would be nice to combine the concepts of two smart people into one.

This is how the TRISC project, the ternary RISC, was born, within which the virtual machine and the Oberon compiler in ternary code were implemented. Also in the framework of this project, a simulator of logic three-way valves was implemented, but more on that another time.

The project was brought to the alpha stage and frozen. And in 2015, in the process of learning the Dart language, the idea arose to implement an emulator port for the browser.
Unusual web project, many strange goals, what could be more interesting?

0 + 0. Goals and means

Since the compiler in the ternary code was already working, I also had the ternary code. Therefore, the main goal of the project is to build a processor emulator. To prevent the task from being reduced to a primitive set of switches, let's assume that the virtual machine must be controlled, asynchronous, so that the page does not freeze - this is the web.

Also, for the sake of interest, you can use your own data types, which will be characteristic of ternary machines, and the processor itself can be implemented as separate modules, roughly corresponding to the actual processor units - registers, ALU, etc. The advantage will be the use of many features of Dart, because the project is needed for self-study.

There is an original interpreter before my eyes, there should be no special problems with the algorithms.

0 ++. Maths

To begin with, we implement logic and mathematics. Immediately interesting.

The basic logical type of the ternary system is trilean (by analogy with boolean). I did not find a Russian equivalent to the word. There are three values ​​for the trilean type, true / null / false. For these values, there are basic logical laws. They were formulated by Yan Lukasevich in the 20s of the last century. Of the two laws, negation and implication, all basic logical operations are derived.
Having described Tril type in Dart, we use operator overloading options.
A bit of testing, and the type is ready. We use the factory constructor in order not to produce multiple copies of objects of type Tril, a kind of optimization.

With integers is also not so simple. The minimum unit of information is trit (by analogy with a bit). In the Setun project, a six-sided triple was used (by analogy with a byte). In my project, I used a nine-day triit to be closer to an eight-bit byte in size. And although at first glance, nine more than eight, this fact pays off the power of the resulting data type - 19,683 values. From -9841 to 9841 inclusive. Without inverse complements, without the need to distinguish arithmetic shift from logical.

In the alternative universe, people in the 80s did not have problems fitting the desired characters to 256 values ​​of one byte. We describe this data type tryte in the Dart language, we implement for it the basic arithmetic operations.

Additionally, we introduce the int27 type, as you can guess, it has 27 trits, this will be the size of the machine word in our system. Of course, 27 trites fit more values ​​than 32 bits. Values ​​range from -3,812,798,742,493 to 3,812,798,742,493. Here you can say that 64 bits will fit more than 27 trits, but you will need twice as many triggers for this register.

For the most demanding, you can enter the type int81, which will tax even 128-bit numbers in the minus. By the way, you can see that the number of trit increases in powers of three.
We implement the int27 type like tryte.

An additional type of our mathematical subsystem will be the Trits type, which is an analogue of the SET type in Oberon. A separate article by N. Wirth is devoted to the type of SET, where he calls the type SET undervalued. We appreciate it.

In short, Trits (SET) is a set of trites. It is freely convertible into an integer, but all basic set operations, addition, multiplication, and so on, are applicable to Trits. Support of this type will simplify the implementation of processing some instructions in the processor. And he will help to convert the triple number into a string.

In addition to the ternary recording of numbers with symbols - / 0 / +, there is also a nine-dimensional form for recording ternary numbers, in it the characters are ZXYW01234. We realize converters for such record of numbers.

As entertainment, not related to the main task - we implement a converter into a threefold symmetric number system with an irrational basis.
The base will choose the square of the golden section. This number system is called Fibonacci's. She has an interesting property - the notation of the number is symmetric about its zero digit.



An example of all converters in one picture.
Let's do some tests. Mathematical subsystem is ready.

+ -. Iron

First, let's describe the memory. It's pretty simple, memory is just an array of tribes. We will supplement it with only one function in the form of an additional class - the ability to read whole words of data.

Additionally, for memory, we will describe the MMU, a device for controlling access to different areas of memory. Our MMU is simple, it allows you to connect to some memory cells as I / O pins, and also allows you to use negative addresses to access these pins from executable programs.

For the processor, I used the asynchronous capabilities of the Dart language. Each processor cycle is scheduled for the future and executed asynchronously. At the same time, I still cheated and sped up execution, having increased the clock frequency by 100 times. It turned out a kind of overclocking. So, the main processor activity occurs in the next () method.

It's time to develop a processor instruction set. As I have already said, I was based on the Oberon 2013 project materials. N. Wirth developed a simple system of commands for implementing his RISC-processor on the FPGA. I upgraded this command system for the ternary code. Two- or three-operand arithmetic, conditional transitions, direct and indirect memory addressing.

The processor will have 27 general-purpose registers, an additional PC register will indicate the address of the location of the next command in memory, the IR register will contain the current command. There is also an additional NZ trit, which will contain the additional result of performing operations on registers. Some general registers will be taken away by the Oberon system for placing return addresses, top of the stack, etc.

As you know, RISC processors usually use separate commands for loading and unloading data into RAM, and all operations are performed on registers and data in them.

So the algorithm of the processor’s actions is the following: the word is read from the memory at the PC address, the value is written to the IR and sent to the command decoder, which sends signals to one or another block to perform actions. Such actions can change the value of the register, while in the NZ register information is written about whether the value is zero or is greater than zero. So, one answer answers two questions. Subsequently, this trit can be used when executing a conditional instruction. As a result of the command execution, the memory state changes in places that the executable code considers variables, the processor transition address changes in the next step, the iteration ends. The processor is terminated when switching to a -1 memory cell, since it contains a command with the format - (-13).

It makes no sense to paint the entire command system. You can read about it in github.com/kpmy/tri/blob/master/doc/trinary-0.pdf .

Communication with the outside world takes place by writing to a memory cell with a predefined address of a value that the host executor will process. For example, you can thus implement a primitive debugging console.
Since we have a web application, we will display this console in an authentic black window with white letters. To do this, we use the ready-made component and the capabilities of the standard Dart library for web content management.

+ -0. The first steps

Since I already had the code from the working virtual machine, I will briefly describe the features of its execution.

So, for the firmware in the memory of the finished code, we describe the class loader, which will download the code from the server and write it into memory. JSON code is strange, but it’s a fact, because any binary recording format would not be completely compatible with the ternary code.

According to the canons of the Oberon system, the bootloader modifies the addresses of the transition; simple mathematics makes an amendment to the code for the code offset of the loadable module relative to the zero position that the compiler sets when compiling.

A separate module is bootstrap, these are several commands that will set machine constants in memory (memory size, module address, etc.) and transfer the processor to the address of the first executable command. Bootstrap was prepared by hand.

The Core module is created in the image and likeness of the Oberon system kernel, the Kernel module, since it is a kernel, there are many direct memory operations in it, an implementation of the allocator of dynamic structures (sometimes buggy), an exception interceptor implementation, etc.
Just in the Core module we implement the most primitive console. To output strings and numbers, we will write the values ​​of characters into a memory cell, as described above. The platform-dependent SYSTEM module is virtual; the compiler translates its calls directly into mash-code.

Inexpressive screenshot.
Check the performance of the resulting virtual machine here . Of course, complex debugging of both the processor and the compiler at the same time led to some bugs (which I haven’t yet found), but as proof of concept, the result of the work seemed sufficient to me.

+ - +. Results

As a result, we got a fully functional, expandable in all directions analogue of the N. Virta processor from the Oberon 2013 project with a modification for the ternary number system and the ternary code and several modules for working in the resulting system.

In the original interpreter, I made an attempt to develop success and realize communication with the outside world by analogy of the rs232 port, with the file system based on the 9p protocol. And that's what I encountered. Both technologies, although they are declared to be cross-platform, when entered into the concept of a platform, the trit and third parties rapidly lose their cross-platform status. The basis in the form of bytes and bits makes porting such technologies a non-trivial task.

Of course, one can argue here that the significance and prevalence of ternary systems is zero, but here, as in a joke about Vovochka, there is a trinity, and there are no words about cross-platform for it. Perhaps this is some brake on the distribution of ternary systems. After all, everything is working.

Personally, I saw only one justified use of ternary machines - this is the organization of communication channels protected from intruders. Indeed, even if there is direct access to the channel, the hacker will need at least a hardware signal decoder, which has yet to be developed. Thus, the fight of armor and projectile can give life to the industrial application of the described technologies.

+ 0-. Links

Well, perhaps a few links for those who are interested.

• trinary.ru beautiful site with calculators, calendars, OS simulator original Setun.
• ternarycomp.cs.msu.ru is a more serious site with a description of patents, algorithms
• www.inf.ethz.ch/personal/wirth/ProjectOberon/index.html Oberon 2013 project author page.
• github.com/kpmy/tri project repository
• bitbucket.org/petryxa/trisc repository of the original emulator

+00. PS

N.P. Brusentsov died on December 4, 2014. I hope his life's work will not be forgotten.