Binary decoder

[piriform]

I'm trying do so some work with boo lean operations in Factorio, and of course the first thing to do is design a binary decoder.
Well, this is my stab at it.


The picture shows an 8 bit decoder capable of translating 0-255.
Description of operation
-each bit is translated by a row of 4 (except msb) combinators. Bit 8 is on top, Bit 1 on the bottom.
-data enters on a green wire to the divider. Carry (from above) is subtracted from input and divided by -2^(n-1) (for bit 8 that would be -2^7 =-128)
-the result is fed to a decider that looks for anything <0. If that is true, decider will generate an appropriate bit ( e.g. "8"=1),
-combinator to the right of the divider generates the carry by multiplying result by 2^(n-1)
-the carry is then propagated to the lower bits via adder on the left.
So the good, the bad and the ugly
The good part is it works
The bad part is it's slow. The ripple carry is brutal (on the order of 3n ticks)
The ugly part, apart from the size, it''s really slow (almost 1/2 second for 8 bits?)
If there is any interest I'll be happy to post the blueprint, although I would not recommend it for anything but a quasi static application.
On the other hand, if anyone knows of a really clever way of doing it with say 10 combinators in 2-3 ticks, I'm all ears.

---------------------------------------------------------------------------------------------------------------------------------------------------------------
PS

Poor Decoder has gone through a lot. From a slow,flabby kid he's become something
If you want to know the real story please click the spoiler. read. Otherwise skip to the end and look at the pictures (sorry I couldn't spoiler the text)

Decoders Tale

The Sad but Ultimately Triumphant Story of Binary Decoder
(Drama in IV parts)

Imprimus (or Parte I)

A long, long time ago (in computer years) Bool and Bit, who up to now, lived in a happily married bliss, felt a certain lack. Their life was incomplete, they needed a Family.
No sooner said than done (after a certain amount of hair pulling etc. - Hey!), a baby was born. Mr. & Mrs. Bool decided to call him Binary Decoder, Decoder in short.
Now, Decoder was not the prettiest boy around (see picture of his early childhood), nor was he quick on his feet (actually he was pretty sloooow, but try telling that to Mrs. Bool). Mr. Bool, of course, was personally offended that his highly refined genes could ever be responsible for progeny such as this, and made a firm decision to improve the er, product. He tried everything, but nothing worked, until in desperation, he started begging strangers for advice.

Secundus (or Parte II)

A kind stranger, took pity on Mr. Bool and offered some advice (you know: diet, exercise, plastic surgery etc.), which Mr. Bool took to heart (and mercilessly imposed upon poor hapless Decoder). All that hard work finally bore fruit. As a teenager, Decoder showed definite improvement. He was leaner, faster and better looking (see picture 2). Mr. Bool was content, his boy was finally someone he could be proud of (sorta).

Tercius (or Parte III)

This state of affairs persisted for some time (in computer years), until one dark, cold night, Mr. Bool thought he heard something. It was as if the Wind, using voice of an ancient warrior (well, Middle Ages, actually) was whispering:“Don't be a Fool, Bool! Decoder could be so much better, if you only used the Force Hardware”.
“How could Decoder be better? What Force Hardware? Poppycock! I am Busy, and have other projects I must attend to” Mr. Bool thought.
But then one day he had a vision. He finally saw what Decoder could become, and was chastened (and despondent and drunk). Decoder could be so much better, if he only knew how to Make It So. He pondered and pondered. He even considered pleading with the Wind, but knew at once, that was foolishness. And then one day, he noticed a clue in the vision Wind had shown him. It was this *. Bool laughed, cried, thought of drinking, but No!, he had Work To Do!
Numbers, BIG ones at that, were the key. He realized, he'd been (and most likely still) a Fool. Blinded by the light, ignoring the obvious (in all fairness not so obvious to all). At once, he firmed his resolve (girded his loins etc.) and planned the campaign of attack.
Needless to say, poor Decoder was not very keen on another round of self-improvement, as scars from the last one had not fully healed. He cried, he whined, he sabotaged his Father's efforts, all to no avail. Mr. Bool was determined that his Will Be Done.

Quartus (You know the Drill)

When, he finally emerged into the light of day, Decoder was glorious. Lean and stripped of all superfluous fat, so powerful he could lift 16 Bits (when she was a young child), almost faster than a speeding tick, so handsome the Combinator Sisters cried.
His sisters: Wood, Stone, and the twins (Ore and Plate), welcomed his (re)emergence onto the Factory Floor. Being always pretty and smart, they were now also very proud of their brother. Finally he could hold his head high, and rejoin them in their Very Important Work.

And all because of kind strangers and whispers of an ancient (OK,OK Middle Ages) warrior borne on the wind.

The End.

[DaveMcW]

Here is a decoder for the 2^4 bit that runs in 3 ticks. You can make a similar one for the other bits and run them in parallel.

The + combinator is just a no-op that adds zero.

[piriform]

Nice! Many thanks. I'll give it a shot ASAP.

--------------------------------------------

Here it is, 8 bits at 30 60 cps!

https://drive.google.com/file/d/0B3I2uZ ... sp=sharing
And the string
https://drive.google.com/file/d/0B3I2uZ ... sp=sharing
Thanks again!

[XKnight]

Try to think out of the box... Factorio is a game and this game is inside computer, use your advantage.

1.png (307.49 KiB) Viewed 44434 times

[DaveMcW]

Very nice, fast modulo arithmetic using integer overflow.

[piriform]

I hate those "think out of the box" as I always get distracted wandering about the colour. But, OK, I'll bite if you tell me how many combinators.


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
lol. So, when is Combinators 201 coming out?
p.s. I smell BIG numbers


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
It's been a trip, but well worth it I think. Thanks for all the help.

[Fatmice]

Does this overflow trick still work? If I am reading this decoder right, you are doing Each * Blue-square, where Each is the signal 0-B, with values 2^(32-n) where n is 1 through 12.

Thus
0 => 2147483648
1 => 1073741824
2 => 536870912
etc...
B => 1048576

Certain numbers do not display right anymore in their binary form since 2147483648 can not be put in.

[Neotix]

I tried to understand that decoder and to do that I reconstructed calculations step by step in excel.
So the combinator multiply all channels signals with input signal. When result is greater than 2^31 then INT is oveflowed and start from -2^31 (it can be overflowed multiple times). That's why some of the channels signals have negative number.
Each light have condition to light up when specific channel signal is < 1.

[piriform]

Certain numbers do not display right anymore in their binary form since 2147483648 can not be put in.

Correct, this is due to the integer definition that Factorio uses where 2^31 is the largest positive #. Decoder should work up to 2^30 (i.e. 30 bits) and maybe up to 2^31-1.

. When result is greater than 2^31 then INT is oveflowed and start from -2^31 (it can be overflowed multiple times). That's why some of the channels signals have negative number.

Exactly, those channels are of course, bits. If you look at my post on Booleans, you will see that I convert them to 1's and then do some bit manipulation.

I tried to understand that decoder and to do that I reconstructed calculations step by step in excel.

+1



PS Normally I try to post an explanation of my circuits. In this case I did not, as the circuit was invented by XKnight.

[Neotix]

In 0.12.29 it's impossible to set 2147483648 number.

[Fatmice]

In 0.12.29 it's impossible to set 2147483648 number.

That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.

[XKnight]

In 0.12.29 it's impossible to set 2147483648 number.

That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.

Nope.

1.png (608.39 KiB) Viewed 38380 times

Although you can find the answer on this question in my contraptions, but I strictly recommend you to come to this answer by yourself. Otherwise you won't understand something important.

[Neotix]

I think I get it.

[Fatmice]

In 0.12.29 it's impossible to set 2147483648 number.

That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.

Nope.

1.png

Although you can find the answer on this question in my contraptions, but I strictly recommend you to come to this answer by yourself. Otherwise you won't understand something important.

I do get what is going on, but 2^31 still can't be set directly. I assumed Piriform had set signal-0 to 2^31...maybe it was possible to do that in the past.. Maybe he set it to 2^31-1, but whatever it was the output confused me.

Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31, which will give the right overflow pattern.

[DaveMcW]

Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31.

Or you could just enter -2147483648 directly.

[Fatmice]

Meh, might just make a mistake. =P

[siggboy]

Here's another, technical, explanation for how the binary decoder by XKnight works (the design that abuses the integer overflow after adding large values):

• Factorio combinators use signed, 32-bit integers.
• Signed integers use "two's complement" notation to store negative values in binary.
• Negative values have the most significant bit set to "1" (that's the bit corresponding to a value of 2^31, because we're dealing with 32-bit integers).
• Multiplying and dividing by 2 (or powers of 2) will shift the bits in a value to the left and right (it's like multiplying and dividing by 10 in the decimal system by way of adding/removing zeroes, only in binary).

So, by repeated doubling you can shift any bit into the most significant position, and if the result is negative, you know that the original value did have a "1" in that position. Repeated doubling is the same as multiplying with a power of two, so it's easy to multiply any bit into the MSB position if you keep the needed powers of two as constants.

This is extremely quirky, although not as bad a looping combinator outputs . On the other hand, it's also very stable and unlikely to stop working unless the size of Factorio registers increases to 64 bits at some point.

[siggboy]

I do get what is going on, but 2^31 still can't be set directly. I assumed Piriform had set signal-0 to 2^31...maybe it was possible to do that in the past.. Maybe he set it to 2^31-1, but whatever it was the output confused me.

Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31, which will give the right overflow pattern.

32-bit signed integers have a range of -2^31 to 2^31-1. This is because positive values have the most significant bit (2^31) set to zero, so the biggest positive value is 0111...111 (a 0 followed by 31 1s).

2^31 not only cannot be set "directly", it actually does not exist. 2^31 exists internally, but for us it is actually the number -2^31.

The highest value you can set manually in a combinator is 2^31-1 (which makes sense, because it's the highest value that actually fits into the combinator...). You can then add "1" to this and it will appear to, kind of, "underflow" to -2^31. In reality, no overflow happens at all (see below), but the convention that the MSB in a signed integer signifies a negative value gives you the appearance that huge overflow took place.

Nice trick of setting two signals to create an implicit sum (and "overflow"), but actually not necessary at all since you can simply set -2^31 directly. You don't have to "trick" the game into generating "2^31" for you (which doesn't exist), because for all intents and purposes "-2^31" is the value you're looking for and you can set it directly; "-2147483648" is accepted as a constant by combinators.

A case could be made for the game simply disallowing overflowing, and adding to a value of 2^31-1 would then do nothing, i.e. result in 2^31-1 again. The same for negative values in the other direction.

To be honest I'm still surprised that the game behaves like plain C and not like a safe language in this area. Somebody who only knows safe languages will probably not ever get the idea and try to abuse two's complement notation to make a bit decoder.

It's wrong to even talk about "integer overflow" in the current context (multiplying until you make the number negative), because no overflow happens. Setting the 32nd bit by way of adding 1 to 2^31-1 is not overflowing, it's a simple carry operation happening.

Overflow happens when you add -1 to -2^31, because what actually happens is that a "1" followed by 31 "0" (the number -2^31) is added to a number consisting of all 1s (the number -1):

Code: Select all

  10000000000000000000000000000000    (32 digits)
+ 11111111111111111111111111111111    (32 digits)
--------------------------------------------------
 101111111111111111111111111111111    (33 digits)

The leftmost "1" in the result above is the 33rd bit, so it does not fit into the result anymore and gets dropped. That's what's commonly known as "a register overflowing" in computer science.

After we drop that extra "1" we end up with

Code: Select all

   01111111111111111111111111111111

which is 2^31-1, the largest positive number. So by subtracting 1 from -2^31 you actually wrap around all the way to 2^31-1...

[Amegatron]

Try to think out of the box... Factorio is a game and this game is inside computer, use your advantage.

1.png

Still can't get it how do you manage do decode a signal using just one combinator :/ All I came to myself is chained combinator pairs, each deviding by 2 and determining whether theres is 1 left after division. This means I have 8 pairs for 8-bit decoding, also working for 8 ticks to decode the value.

The first "/" combinator in row devides the incoming value by 2.
The second "*" combinator multiplies the result of previous one by -2.
Then the output then goes to the third "*" combinator which converts the signal (which is 1 or 0) into another signal, which is used as a bit for the screen e.g.
The output from first comb-r goes to the next row, chaining the division by 2 further.

EDIT: I think I got it, read carefully previous comments )

[Amegatron]

At last I reproduced the decoder.

But I met some strange thing. For first 13 signals, their value must be ((2^(31-n)) + 1), and first signal equalling -2147483647. But the rest signals must be (2^(31-n)), without additional 1. Though I could not explain why I noticed that while testing on different values and I also suppose there can be some incorrect decodings with these signals ...