-
Notifications
You must be signed in to change notification settings - Fork 95
/
converter.go
191 lines (164 loc) · 6.47 KB
/
converter.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
// Package kerl implements the Kerl hashing function.
package kerl
import (
. "github.com/iotaledger/iota.go/consts"
"github.com/iotaledger/iota.go/kerl/bigint"
. "github.com/iotaledger/iota.go/trinary"
"github.com/pkg/errors"
)
const (
// the middle of the domain described by one tryte
halfTryte = TryteRadix / 2
// largest number of trytes that can be represented as a uint32
trytesPerUint32 = 6
// radix used in the uint32 chunk conversion, i.e. 27^trytesPerUint32
uint32Radix = 387420489
// number of uint32 chunks to represent the hash, i.e. ceil(HashTrytesSize / trytesPerUint32)
hashUint32Size = (HashTrytesSize + trytesPerUint32 - 1) / trytesPerUint32
)
var (
// maxTer243 represents the largest value that can be represented in 243-trit balanced ternary, i.e. ⌊3²⁴³ / 2⌋.
// since ⌊3²⁴³ / 2⌋ cannot be expressed in 384 bits, it only consists of its lower 384 bits.
maxTer243 = bigint.MustParseU384("0x1b3dc3cef97f039efe13f810fde381a1da330aa36cee5506f1c6d805246cd94ab09a028b3d8cf0eedd01633cf16b9c2d")
// maxTer242 represents the largest value that can be represented in 242-trit balanced ternary, i.e. ⌊3²⁴² / 2⌋.
maxTer242 = bigint.MustParseU384("0x5e69ebefa87fabdfaa06a805a9f6808b48bbae3679a4c70250979d570c24486e3ade00d91484504f9f007669a5ce8964")
// maxTer242 represents the smallest value that can be represented in 242-trit balanced ternary, i.e. -⌊3²⁴² / 2⌋.
minTer242 = bigint.MustParseU384("0xa19614105780542055f957fa56097f74b74451c9865b38fdaf6862a8f3dbb791c521ff26eb7bafb060ff89965a31769c")
// trit243 represents the value of the 243rd trit, i.e. 3²⁴².
trit243 = bigint.MustParseU384("0xbcd3d7df50ff57bf540d500b53ed011691775c6cf3498e04a12f3aae184890dc75bc01b22908a09f3e00ecd34b9d12c9")
)
func tryteValuesToTrits(vs []int8) Trits {
trits := make([]int8, len(vs)*TritsPerTryte)
for i, v := range vs {
MustPutTryteTrits(trits[i*TritsPerTryte:], v)
}
return trits
}
func tryteValuesToTrytes(vs []int8) Trytes {
if len(vs) != HashTrytesSize {
panic(ErrInvalidTrytesLength) // bounds check hint to compiler
}
trytes := make([]byte, HashTrytesSize)
for i := range vs {
trytes[i] = MustTryteValueToTryte(vs[i])
}
return string(trytes)
}
// tryteValueZeroLastTrit returns the value of tryte v, with the last trit set to zero.
// It takes a tryte value of three trits a+3b+9c and returns a+3b.
func tryteValueZeroLastTrit(v int8) int8 {
if v > 4 {
return v - 9
}
if v < -4 {
return v + 9
}
return v
}
func tryteValuesToBytes(vs []int8) []byte {
if len(vs) != HashTrytesSize { // hint to the compiler that vs has constant length
panic(ErrInvalidTrytesLength)
}
// assure that the last trit is zero
vs[HashTrytesSize-1] = tryteValueZeroLastTrit(vs[HashTrytesSize-1])
// convert the balanced ternary input to base 27⁶, the largest power of 27 still fitting into an uint32
// add ⌊27 / 2⌋ to each tryte value to get base 27
cs := make([]uint32, hashUint32Size)
for i := range cs {
for j := trytesPerUint32 - 1; j >= 0; j-- {
idx := uint(i*trytesPerUint32 + j) // hint to the compiler that idx is always non-negative
if idx < HashTrytesSize {
cs[i] = TryteRadix*cs[i] + uint32(vs[idx]+halfTryte)
}
}
}
// convert the base 27⁶ number to a 384-bit unsigned integer
b := bigint.U384()
bs := b.Words()[:0] // do not modify b directly, but work on a new slice backed by the same array
for i := len(cs) - 1; i >= 0; i-- {
n := len(bs)
// multiply by the radix and add the value of the next chunk
carry := cs[i]
for i := 0; i < n; i++ {
v := uint32Radix*uint64(bs[i]) + uint64(carry)
carry, bs[i] = uint32(v>>32), uint32(v)
}
// increase length of slice if necessary
if carry > 0 && n < cap(bs) {
bs = append(bs, carry)
}
}
// since we initially added ⌊27 / 2⌋ to each of the 81 tryte values, we now need to subtract ⌊27⁸¹ / 2⌋ = ⌊3²⁴³ / 2⌋
// this leads the correct two's complement representation for negative numbers
b.Sub(maxTer243)
// return the corresponding byte slice
bytes := make([]byte, HashBytesSize)
b.Read(bytes)
return bytes
}
// KerlBytesZeroLastTrit changes a chunk of 48 bytes so that the corresponding ternary number has 242th trit set to 0.
func KerlBytesZeroLastTrit(bytes []byte) {
// bytes represents a signed 384-bit integer
b := bigint.U384()
b.SetBytes(bytes)
// assure that the value is in [-⌊3²⁴² / 2⌋, ⌊3²⁴² / 2⌋]
if b.MSB() != 0 {
if b.Cmp(minTer242) >= 0 {
return
}
// add 3²⁴² if the last trit was -1, i.e. if the value is less than -⌊3²⁴² / 2⌋
b.Add(trit243)
} else {
if b.Cmp(maxTer242) <= 0 {
return
}
// subtract 3²⁴² if the last trit was 1, i.e. if the value is greater than ⌊3²⁴² / 2⌋
b.Sub(trit243)
}
// update the bytes if we made changes
b.Read(bytes)
}
// KerlTritsToBytes is only defined for hashes, i.e. chunks of trits of length 243. It returns 48 bytes.
func KerlTritsToBytes(trits Trits) ([]byte, error) {
if !CanBeHash(trits) {
return nil, errors.Wrapf(ErrInvalidTritsLength, "must be %d in size", HashTrinarySize)
}
// convert to tryte values
vs := make([]int8, HashTrytesSize)
for i := range vs {
tryteTrits := trits[i*TritsPerTryte:]
_ = tryteTrits[2] // bounds check hint to compiler
vs[i] = tryteTrits[0] + tryteTrits[1]*3 + tryteTrits[2]*9
}
return tryteValuesToBytes(vs), nil
}
// KerlTrytesToBytes is only defined for hashes, i.e. chunks of trytes of length 81. It returns 48 bytes.
func KerlTrytesToBytes(trytes Trytes) ([]byte, error) {
if len(trytes) != HashTrytesSize {
return nil, errors.Wrapf(ErrInvalidTrytesLength, "must be %d in size", HashBytesSize)
}
// convert to tryte values
vs := make([]int8, HashTrytesSize)
for i := 0; i < HashTrytesSize; i++ {
vs[i] = MustTryteToTryteValue(trytes[i])
}
return tryteValuesToBytes(vs), nil
}
// KerlBytesToTrits is only defined for hashes, i.e. chunks of 48 bytes. It returns 243 trits.
func KerlBytesToTrits(b []byte) (Trits, error) {
if len(b) != HashBytesSize {
return nil, errors.Wrapf(ErrInvalidBytesLength, "must be %d in size", HashBytesSize)
}
vs := make([]int8, HashTrytesSize)
bytesToTryteValues(b, vs)
return tryteValuesToTrits(vs), nil
}
// KerlBytesToTrytes is only defined for hashes, i.e. chunks of 48 bytes. It returns 81 trytes.
func KerlBytesToTrytes(b []byte) (Trytes, error) {
if len(b) != HashBytesSize {
return "", errors.Wrapf(ErrInvalidBytesLength, "must be %d in size", HashBytesSize)
}
vs := make([]int8, HashTrytesSize)
bytesToTryteValues(b, vs)
return tryteValuesToTrytes(vs), nil
}