stack.go
1 // Copyright (c) 2013-2017 The btcsuite developers 2 // Use of this source code is governed by an ISC 3 // license that can be found in the LICENSE file. 4 5 package txscript 6 7 import ( 8 "encoding/hex" 9 "fmt" 10 ) 11 12 // asBool gets the boolean value of the byte array. 13 func asBool(t []byte) bool { 14 for i := range t { 15 if t[i] != 0 { 16 // Negative 0 is also considered false. 17 if i == len(t)-1 && t[i] == 0x80 { 18 return false 19 } 20 return true 21 } 22 } 23 return false 24 } 25 26 // fromBool converts a boolean into the appropriate byte array. 27 func fromBool(v bool) []byte { 28 if v { 29 return []byte{1} 30 } 31 return nil 32 } 33 34 // stack represents a stack of immutable objects to be used with bitcoin 35 // scripts. Objects may be shared, therefore in usage if a value is to be 36 // changed it *must* be deep-copied first to avoid changing other values on the 37 // stack. 38 type stack struct { 39 stk [][]byte 40 verifyMinimalData bool 41 } 42 43 // Depth returns the number of items on the stack. 44 func (s *stack) Depth() int32 { 45 return int32(len(s.stk)) 46 } 47 48 // PushByteArray adds the given back array to the top of the stack. 49 // 50 // Stack transformation: [... x1 x2] -> [... x1 x2 data] 51 func (s *stack) PushByteArray(so []byte) { 52 s.stk = append(s.stk, so) 53 } 54 55 // PushInt converts the provided scriptNum to a suitable byte array then pushes 56 // it onto the top of the stack. 57 // 58 // Stack transformation: [... x1 x2] -> [... x1 x2 int] 59 func (s *stack) PushInt(val scriptNum) { 60 s.PushByteArray(val.Bytes()) 61 } 62 63 // PushBool converts the provided boolean to a suitable byte array then pushes 64 // it onto the top of the stack. 65 // 66 // Stack transformation: [... x1 x2] -> [... x1 x2 bool] 67 func (s *stack) PushBool(val bool) { 68 s.PushByteArray(fromBool(val)) 69 } 70 71 // PopByteArray pops the value off the top of the stack and returns it. 72 // 73 // Stack transformation: [... x1 x2 x3] -> [... x1 x2] 74 func (s *stack) PopByteArray() ([]byte, error) { 75 return s.nipN(0) 76 } 77 78 // PopInt pops the value off the top of the stack, converts it into a script 79 // num, and returns it. The act of converting to a script num enforces the 80 // consensus rules imposed on data interpreted as numbers. 81 // 82 // Stack transformation: [... x1 x2 x3] -> [... x1 x2] 83 func (s *stack) PopInt() (scriptNum, error) { 84 so, err := s.PopByteArray() 85 if err != nil { 86 return 0, err 87 } 88 89 return makeScriptNum(so, s.verifyMinimalData, defaultScriptNumLen) 90 } 91 92 // PopBool pops the value off the top of the stack, converts it into a bool, and 93 // returns it. 94 // 95 // Stack transformation: [... x1 x2 x3] -> [... x1 x2] 96 func (s *stack) PopBool() (bool, error) { 97 so, err := s.PopByteArray() 98 if err != nil { 99 return false, err 100 } 101 102 return asBool(so), nil 103 } 104 105 // PeekByteArray returns the Nth item on the stack without removing it. 106 func (s *stack) PeekByteArray(idx int32) ([]byte, error) { 107 sz := int32(len(s.stk)) 108 if idx < 0 || idx >= sz { 109 str := fmt.Sprintf("index %d is invalid for stack size %d", idx, 110 sz) 111 return nil, scriptError(ErrInvalidStackOperation, str) 112 } 113 114 return s.stk[sz-idx-1], nil 115 } 116 117 // PeekInt returns the Nth item on the stack as a script num without removing 118 // it. The act of converting to a script num enforces the consensus rules 119 // imposed on data interpreted as numbers. 120 func (s *stack) PeekInt(idx int32) (scriptNum, error) { 121 so, err := s.PeekByteArray(idx) 122 if err != nil { 123 return 0, err 124 } 125 126 return makeScriptNum(so, s.verifyMinimalData, defaultScriptNumLen) 127 } 128 129 // PeekBool returns the Nth item on the stack as a bool without removing it. 130 func (s *stack) PeekBool(idx int32) (bool, error) { 131 so, err := s.PeekByteArray(idx) 132 if err != nil { 133 return false, err 134 } 135 136 return asBool(so), nil 137 } 138 139 // nipN is an internal function that removes the nth item on the stack and 140 // returns it. 141 // 142 // Stack transformation: 143 // nipN(0): [... x1 x2 x3] -> [... x1 x2] 144 // nipN(1): [... x1 x2 x3] -> [... x1 x3] 145 // nipN(2): [... x1 x2 x3] -> [... x2 x3] 146 func (s *stack) nipN(idx int32) ([]byte, error) { 147 sz := int32(len(s.stk)) 148 if idx < 0 || idx > sz-1 { 149 str := fmt.Sprintf("index %d is invalid for stack size %d", idx, 150 sz) 151 return nil, scriptError(ErrInvalidStackOperation, str) 152 } 153 154 so := s.stk[sz-idx-1] 155 if idx == 0 { 156 s.stk = s.stk[:sz-1] 157 } else if idx == sz-1 { 158 s1 := make([][]byte, sz-1) 159 copy(s1, s.stk[1:]) 160 s.stk = s1 161 } else { 162 s1 := s.stk[sz-idx : sz] 163 s.stk = s.stk[:sz-idx-1] 164 s.stk = append(s.stk, s1...) 165 } 166 return so, nil 167 } 168 169 // NipN removes the Nth object on the stack 170 // 171 // Stack transformation: 172 // NipN(0): [... x1 x2 x3] -> [... x1 x2] 173 // NipN(1): [... x1 x2 x3] -> [... x1 x3] 174 // NipN(2): [... x1 x2 x3] -> [... x2 x3] 175 func (s *stack) NipN(idx int32) error { 176 _, err := s.nipN(idx) 177 return err 178 } 179 180 // Tuck copies the item at the top of the stack and inserts it before the 2nd 181 // to top item. 182 // 183 // Stack transformation: [... x1 x2] -> [... x2 x1 x2] 184 func (s *stack) Tuck() error { 185 so2, err := s.PopByteArray() 186 if err != nil { 187 return err 188 } 189 so1, err := s.PopByteArray() 190 if err != nil { 191 return err 192 } 193 s.PushByteArray(so2) // stack [... x2] 194 s.PushByteArray(so1) // stack [... x2 x1] 195 s.PushByteArray(so2) // stack [... x2 x1 x2] 196 197 return nil 198 } 199 200 // DropN removes the top N items from the stack. 201 // 202 // Stack transformation: 203 // DropN(1): [... x1 x2] -> [... x1] 204 // DropN(2): [... x1 x2] -> [...] 205 func (s *stack) DropN(n int32) error { 206 if n < 1 { 207 str := fmt.Sprintf("attempt to drop %d items from stack", n) 208 return scriptError(ErrInvalidStackOperation, str) 209 } 210 211 for ; n > 0; n-- { 212 _, err := s.PopByteArray() 213 if err != nil { 214 return err 215 } 216 } 217 return nil 218 } 219 220 // DupN duplicates the top N items on the stack. 221 // 222 // Stack transformation: 223 // DupN(1): [... x1 x2] -> [... x1 x2 x2] 224 // DupN(2): [... x1 x2] -> [... x1 x2 x1 x2] 225 func (s *stack) DupN(n int32) error { 226 if n < 1 { 227 str := fmt.Sprintf("attempt to dup %d stack items", n) 228 return scriptError(ErrInvalidStackOperation, str) 229 } 230 231 // Iteratively duplicate the value n-1 down the stack n times. 232 // This leaves an in-order duplicate of the top n items on the stack. 233 for i := n; i > 0; i-- { 234 so, err := s.PeekByteArray(n - 1) 235 if err != nil { 236 return err 237 } 238 s.PushByteArray(so) 239 } 240 return nil 241 } 242 243 // RotN rotates the top 3N items on the stack to the left N times. 244 // 245 // Stack transformation: 246 // RotN(1): [... x1 x2 x3] -> [... x2 x3 x1] 247 // RotN(2): [... x1 x2 x3 x4 x5 x6] -> [... x3 x4 x5 x6 x1 x2] 248 func (s *stack) RotN(n int32) error { 249 if n < 1 { 250 str := fmt.Sprintf("attempt to rotate %d stack items", n) 251 return scriptError(ErrInvalidStackOperation, str) 252 } 253 254 // Nip the 3n-1th item from the stack to the top n times to rotate 255 // them up to the head of the stack. 256 entry := 3*n - 1 257 for i := n; i > 0; i-- { 258 so, err := s.nipN(entry) 259 if err != nil { 260 return err 261 } 262 263 s.PushByteArray(so) 264 } 265 return nil 266 } 267 268 // SwapN swaps the top N items on the stack with those below them. 269 // 270 // Stack transformation: 271 // SwapN(1): [... x1 x2] -> [... x2 x1] 272 // SwapN(2): [... x1 x2 x3 x4] -> [... x3 x4 x1 x2] 273 func (s *stack) SwapN(n int32) error { 274 if n < 1 { 275 str := fmt.Sprintf("attempt to swap %d stack items", n) 276 return scriptError(ErrInvalidStackOperation, str) 277 } 278 279 entry := 2*n - 1 280 for i := n; i > 0; i-- { 281 // Swap 2n-1th entry to top. 282 so, err := s.nipN(entry) 283 if err != nil { 284 return err 285 } 286 287 s.PushByteArray(so) 288 } 289 return nil 290 } 291 292 // OverN copies N items N items back to the top of the stack. 293 // 294 // Stack transformation: 295 // OverN(1): [... x1 x2 x3] -> [... x1 x2 x3 x2] 296 // OverN(2): [... x1 x2 x3 x4] -> [... x1 x2 x3 x4 x1 x2] 297 func (s *stack) OverN(n int32) error { 298 if n < 1 { 299 str := fmt.Sprintf("attempt to perform over on %d stack items", 300 n) 301 return scriptError(ErrInvalidStackOperation, str) 302 } 303 304 // Copy 2n-1th entry to top of the stack. 305 entry := 2*n - 1 306 for ; n > 0; n-- { 307 so, err := s.PeekByteArray(entry) 308 if err != nil { 309 return err 310 } 311 s.PushByteArray(so) 312 } 313 314 return nil 315 } 316 317 // PickN copies the item N items back in the stack to the top. 318 // 319 // Stack transformation: 320 // PickN(0): [x1 x2 x3] -> [x1 x2 x3 x3] 321 // PickN(1): [x1 x2 x3] -> [x1 x2 x3 x2] 322 // PickN(2): [x1 x2 x3] -> [x1 x2 x3 x1] 323 func (s *stack) PickN(n int32) error { 324 so, err := s.PeekByteArray(n) 325 if err != nil { 326 return err 327 } 328 s.PushByteArray(so) 329 330 return nil 331 } 332 333 // RollN moves the item N items back in the stack to the top. 334 // 335 // Stack transformation: 336 // RollN(0): [x1 x2 x3] -> [x1 x2 x3] 337 // RollN(1): [x1 x2 x3] -> [x1 x3 x2] 338 // RollN(2): [x1 x2 x3] -> [x2 x3 x1] 339 func (s *stack) RollN(n int32) error { 340 so, err := s.nipN(n) 341 if err != nil { 342 return err 343 } 344 345 s.PushByteArray(so) 346 347 return nil 348 } 349 350 // String returns the stack in a readable format. 351 func (s *stack) String() string { 352 var result string 353 for _, stack := range s.stk { 354 if len(stack) == 0 { 355 result += "00000000 <empty>\n" 356 } 357 result += hex.Dump(stack) 358 } 359 360 return result 361 }