Algorithm for converting a 128-bit value to a string

Question

I am trying to convert 128-bit data to a string in a PLC, but the PLC has max. 32-bit data. I store 128-bit data as a byte array and bit array. Now I need to convert this value to a string, but the PLC does not have such a variable. I did some research, but I couldn't find the answers I wanted.

Basically I need to add the remaining numbers after multiplying their multiples in the binary system to convert a bit array to decimal. But since the number has grown so much, I can't do such a process on the PLC.

My thought is that basically the whole system is processed in binary, and it should split my 128-bit array and convert it to decimal numbers in chunks. Am I thinking wrong?

A 128-bit number has 39 characters. When you convert this number to a byte array, 16 bytes are obtained, so 16*8=128 bits. I need to expand this byte array or bit array to 39 characters again, and I have to do this without using 64-bit or 128-bit variables. I can use max. 32-bit variables.

Does anyone have any information or ideas on the subject?

---

I haven't had time to try the methods, but the threads may be useful for other friends.

@benmiller >> https://stackoverflow.com/questions/57845464/fastest-algorithm-to-convert-hexadecimal-numbers-into-decimal-form-without-using

@davetweed >> https://en.wikipedia.org/wiki/Double_dabble

https://en.wikipedia.org/wiki/Base64

https://en.wikipedia.org/wiki/Ascii85

@greybeard >> "chunk-wise two-step"

Thank you for your support. special thanks:@benmiller , @davetweed , @greybeard

Answer 1

There are basically two ways to convert a natural number from base \$b\$ to base \$B\$:
(Following the diction of D.E. Knuth: TAoCP vol 2: Seminumerical Algorithms 4.4: Radix Conversion)

• Method (1a): Division by \$B\$ (using base \$b\$ arithmetic) (bin2dec: Division by 10)
• Method (1b): Multiplication by \$b\$ (using base \$B\$ arithmetic) (* powers of 2 "in base 10(ᵏ)")

I find "long division" a more intimidating prospect than long multiplication and suggest using 1b: computing with parts "a power of 10" - never mind how arithmetic is done "within parts".
Converting chunks of 10 bits to "millipeds" of 3 decimal digits is a bit more intuitive for a low number of chunks. Once it is working, little of the source code should change switching to groups of 4 digits (and 14-16 bits).
There sort of are two ways to go about this multiplication:

• by parameter part
  (including double dabble for a smart name for a basic (1 bit at a time) method)
  + doesn't need any precomputation/table(s)
  - (I think it's) more operations
• by result part (some like to call this Vedic)
  + (I think it's) less operations
  - needs precomputation/table(s)

Answer 2

Assuming you have BCD addition with carry available you could store 128 39-nibble constants (maybe packed 4 digits per word, but it doesn't matter as long as you can implement extensible BCD addition) representing the BCD value of 2^i for i = 0..127.

Then you iterate through the 128 bits of the unknown value, doing a BCD add of the constant (starting from zero, of course) for each '1' in the original value (and no addition if there is a zero). This is essentially multiplication with a BCD result. There's also the 'add 6' algorithm for BCD correction if BCD operations are not native.

so the array of constants would be {1, 2, 4, ... , 85070591730234615865843651857942052864, 170141183460469231731687303715884105728}

Perhaps a bit slow, but it's hard to go wrong.

If you didn't want to pre-compute the constants you could just add a register to itself in BCD, starting from 1 and compute the constants on the fly, which would take at least twice as long.