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