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 5package txscript 6 7import ( 8 "encoding/hex" 9 "fmt" 10) 11 12// asBool gets the boolean value of the byte array. 13func 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. 27func 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. 38type stack struct { 39 stk [][]byte 40 verifyMinimalData bool 41} 42 43// Depth returns the number of items on the stack. 44func (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] 51func (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] 59func (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] 67func (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] 74func (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] 83func (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] 96func (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. 106func (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. 120func (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. 130func (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] 146func (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] 175func (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] 184func (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] -> [...] 205func (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] 225func (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] 248func (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] 273func (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] 297func (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] 323func (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] 339func (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. 351func (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} 362