protocol/vm/ops.go

   1 package vm
   2
   3 import (
   4         "encoding/binary"
   5         "fmt"
   6         "math"
   7         "reflect"
   8
   9         "github.com/bytom/vapor/errors"
  10         "github.com/bytom/vapor/math/checked"
  11 )
  12
  13 type Op uint8
  14
  15 func (op Op) String() string {
  16         return ops[op].name
  17 }
  18
  19 type Instruction struct {
  20         Op   Op
  21         Len  uint32
  22         Data []byte
  23 }
  24
  25 const (
  26         OP_FALSE Op = 0x00
  27         OP_0     Op = 0x00 // synonym
  28
  29         OP_1    Op = 0x51
  30         OP_TRUE Op = 0x51 // synonym
  31
  32         OP_2  Op = 0x52
  33         OP_3  Op = 0x53
  34         OP_4  Op = 0x54
  35         OP_5  Op = 0x55
  36         OP_6  Op = 0x56
  37         OP_7  Op = 0x57
  38         OP_8  Op = 0x58
  39         OP_9  Op = 0x59
  40         OP_10 Op = 0x5a
  41         OP_11 Op = 0x5b
  42         OP_12 Op = 0x5c
  43         OP_13 Op = 0x5d
  44         OP_14 Op = 0x5e
  45         OP_15 Op = 0x5f
  46         OP_16 Op = 0x60
  47
  48         OP_DATA_1  Op = 0x01
  49         OP_DATA_2  Op = 0x02
  50         OP_DATA_3  Op = 0x03
  51         OP_DATA_4  Op = 0x04
  52         OP_DATA_5  Op = 0x05
  53         OP_DATA_6  Op = 0x06
  54         OP_DATA_7  Op = 0x07
  55         OP_DATA_8  Op = 0x08
  56         OP_DATA_9  Op = 0x09
  57         OP_DATA_10 Op = 0x0a
  58         OP_DATA_11 Op = 0x0b
  59         OP_DATA_12 Op = 0x0c
  60         OP_DATA_13 Op = 0x0d
  61         OP_DATA_14 Op = 0x0e
  62         OP_DATA_15 Op = 0x0f
  63         OP_DATA_16 Op = 0x10
  64         OP_DATA_17 Op = 0x11
  65         OP_DATA_18 Op = 0x12
  66         OP_DATA_19 Op = 0x13
  67         OP_DATA_20 Op = 0x14
  68         OP_DATA_21 Op = 0x15
  69         OP_DATA_22 Op = 0x16
  70         OP_DATA_23 Op = 0x17
  71         OP_DATA_24 Op = 0x18
  72         OP_DATA_25 Op = 0x19
  73         OP_DATA_26 Op = 0x1a
  74         OP_DATA_27 Op = 0x1b
  75         OP_DATA_28 Op = 0x1c
  76         OP_DATA_29 Op = 0x1d
  77         OP_DATA_30 Op = 0x1e
  78         OP_DATA_31 Op = 0x1f
  79         OP_DATA_32 Op = 0x20
  80         OP_DATA_33 Op = 0x21
  81         OP_DATA_34 Op = 0x22
  82         OP_DATA_35 Op = 0x23
  83         OP_DATA_36 Op = 0x24
  84         OP_DATA_37 Op = 0x25
  85         OP_DATA_38 Op = 0x26
  86         OP_DATA_39 Op = 0x27
  87         OP_DATA_40 Op = 0x28
  88         OP_DATA_41 Op = 0x29
  89         OP_DATA_42 Op = 0x2a
  90         OP_DATA_43 Op = 0x2b
  91         OP_DATA_44 Op = 0x2c
  92         OP_DATA_45 Op = 0x2d
  93         OP_DATA_46 Op = 0x2e
  94         OP_DATA_47 Op = 0x2f
  95         OP_DATA_48 Op = 0x30
  96         OP_DATA_49 Op = 0x31
  97         OP_DATA_50 Op = 0x32
  98         OP_DATA_51 Op = 0x33
  99         OP_DATA_52 Op = 0x34
 100         OP_DATA_53 Op = 0x35
 101         OP_DATA_54 Op = 0x36
 102         OP_DATA_55 Op = 0x37
 103         OP_DATA_56 Op = 0x38
 104         OP_DATA_57 Op = 0x39
 105         OP_DATA_58 Op = 0x3a
 106         OP_DATA_59 Op = 0x3b
 107         OP_DATA_60 Op = 0x3c
 108         OP_DATA_61 Op = 0x3d
 109         OP_DATA_62 Op = 0x3e
 110         OP_DATA_63 Op = 0x3f
 111         OP_DATA_64 Op = 0x40
 112         OP_DATA_65 Op = 0x41
 113         OP_DATA_66 Op = 0x42
 114         OP_DATA_67 Op = 0x43
 115         OP_DATA_68 Op = 0x44
 116         OP_DATA_69 Op = 0x45
 117         OP_DATA_70 Op = 0x46
 118         OP_DATA_71 Op = 0x47
 119         OP_DATA_72 Op = 0x48
 120         OP_DATA_73 Op = 0x49
 121         OP_DATA_74 Op = 0x4a
 122         OP_DATA_75 Op = 0x4b
 123
 124         OP_PUSHDATA1 Op = 0x4c
 125         OP_PUSHDATA2 Op = 0x4d
 126         OP_PUSHDATA4 Op = 0x4e
 127         OP_1NEGATE   Op = 0x4f
 128         OP_NOP       Op = 0x61
 129
 130         OP_JUMP           Op = 0x63
 131         OP_JUMPIF         Op = 0x64
 132         OP_VERIFY         Op = 0x69
 133         OP_FAIL           Op = 0x6a
 134         OP_CHECKPREDICATE Op = 0xc0
 135
 136         OP_TOALTSTACK   Op = 0x6b
 137         OP_FROMALTSTACK Op = 0x6c
 138         OP_2DROP        Op = 0x6d
 139         OP_2DUP         Op = 0x6e
 140         OP_3DUP         Op = 0x6f
 141         OP_2OVER        Op = 0x70
 142         OP_2ROT         Op = 0x71
 143         OP_2SWAP        Op = 0x72
 144         OP_IFDUP        Op = 0x73
 145         OP_DEPTH        Op = 0x74
 146         OP_DROP         Op = 0x75
 147         OP_DUP          Op = 0x76
 148         OP_NIP          Op = 0x77
 149         OP_OVER         Op = 0x78
 150         OP_PICK         Op = 0x79
 151         OP_ROLL         Op = 0x7a
 152         OP_ROT          Op = 0x7b
 153         OP_SWAP         Op = 0x7c
 154         OP_TUCK         Op = 0x7d
 155
 156         OP_CAT         Op = 0x7e
 157         OP_SUBSTR      Op = 0x7f
 158         OP_LEFT        Op = 0x80
 159         OP_RIGHT       Op = 0x81
 160         OP_SIZE        Op = 0x82
 161         OP_CATPUSHDATA Op = 0x89
 162
 163         OP_INVERT      Op = 0x83
 164         OP_AND         Op = 0x84
 165         OP_OR          Op = 0x85
 166         OP_XOR         Op = 0x86
 167         OP_EQUAL       Op = 0x87
 168         OP_EQUALVERIFY Op = 0x88
 169
 170         OP_1ADD               Op = 0x8b
 171         OP_1SUB               Op = 0x8c
 172         OP_2MUL               Op = 0x8d
 173         OP_2DIV               Op = 0x8e
 174         OP_NEGATE             Op = 0x8f
 175         OP_ABS                Op = 0x90
 176         OP_NOT                Op = 0x91
 177         OP_0NOTEQUAL          Op = 0x92
 178         OP_ADD                Op = 0x93
 179         OP_SUB                Op = 0x94
 180         OP_MUL                Op = 0x95
 181         OP_DIV                Op = 0x96
 182         OP_MOD                Op = 0x97
 183         OP_LSHIFT             Op = 0x98
 184         OP_RSHIFT             Op = 0x99
 185         OP_BOOLAND            Op = 0x9a
 186         OP_BOOLOR             Op = 0x9b
 187         OP_NUMEQUAL           Op = 0x9c
 188         OP_NUMEQUALVERIFY     Op = 0x9d
 189         OP_NUMNOTEQUAL        Op = 0x9e
 190         OP_LESSTHAN           Op = 0x9f
 191         OP_GREATERTHAN        Op = 0xa0
 192         OP_LESSTHANOREQUAL    Op = 0xa1
 193         OP_GREATERTHANOREQUAL Op = 0xa2
 194         OP_MIN                Op = 0xa3
 195         OP_MAX                Op = 0xa4
 196         OP_WITHIN             Op = 0xa5
 197         OP_MULFRACTION        Op = 0xa6
 198
 199         OP_SHA256        Op = 0xa8
 200         OP_SHA3          Op = 0xaa
 201         OP_HASH160       Op = 0xab
 202         OP_CHECKSIG      Op = 0xac
 203         OP_CHECKMULTISIG Op = 0xad
 204         OP_TXSIGHASH     Op = 0xae
 205
 206         OP_CHECKOUTPUT Op = 0xc1
 207         OP_ASSET       Op = 0xc2
 208         OP_AMOUNT      Op = 0xc3
 209         OP_PROGRAM     Op = 0xc4
 210         OP_INDEX       Op = 0xc9
 211         OP_ENTRYID     Op = 0xca
 212         OP_OUTPUTID    Op = 0xcb
 213         OP_BLOCKHEIGHT Op = 0xcd
 214 )
 215
 216 type opInfo struct {
 217         op   Op
 218         name string
 219         fn   func(*virtualMachine) error
 220 }
 221
 222 var (
 223         ops = [256]opInfo{
 224                 // data pushing
 225                 OP_FALSE: {OP_FALSE, "FALSE", opFalse},
 226
 227                 // sic: the PUSHDATA ops all share an implementation
 228                 OP_PUSHDATA1: {OP_PUSHDATA1, "PUSHDATA1", opPushdata},
 229                 OP_PUSHDATA2: {OP_PUSHDATA2, "PUSHDATA2", opPushdata},
 230                 OP_PUSHDATA4: {OP_PUSHDATA4, "PUSHDATA4", opPushdata},
 231
 232                 OP_1NEGATE: {OP_1NEGATE, "1NEGATE", op1Negate},
 233
 234                 OP_NOP: {OP_NOP, "NOP", opNop},
 235
 236                 // control flow
 237                 OP_JUMP:   {OP_JUMP, "JUMP", opJump},
 238                 OP_JUMPIF: {OP_JUMPIF, "JUMPIF", opJumpIf},
 239
 240                 OP_VERIFY: {OP_VERIFY, "VERIFY", opVerify},
 241                 OP_FAIL:   {OP_FAIL, "FAIL", opFail},
 242
 243                 OP_TOALTSTACK:   {OP_TOALTSTACK, "TOALTSTACK", opToAltStack},
 244                 OP_FROMALTSTACK: {OP_FROMALTSTACK, "FROMALTSTACK", opFromAltStack},
 245                 OP_2DROP:        {OP_2DROP, "2DROP", op2Drop},
 246                 OP_2DUP:         {OP_2DUP, "2DUP", op2Dup},
 247                 OP_3DUP:         {OP_3DUP, "3DUP", op3Dup},
 248                 OP_2OVER:        {OP_2OVER, "2OVER", op2Over},
 249                 OP_2ROT:         {OP_2ROT, "2ROT", op2Rot},
 250                 OP_2SWAP:        {OP_2SWAP, "2SWAP", op2Swap},
 251                 OP_IFDUP:        {OP_IFDUP, "IFDUP", opIfDup},
 252                 OP_DEPTH:        {OP_DEPTH, "DEPTH", opDepth},
 253                 OP_DROP:         {OP_DROP, "DROP", opDrop},
 254                 OP_DUP:          {OP_DUP, "DUP", opDup},
 255                 OP_NIP:          {OP_NIP, "NIP", opNip},
 256                 OP_OVER:         {OP_OVER, "OVER", opOver},
 257                 OP_PICK:         {OP_PICK, "PICK", opPick},
 258                 OP_ROLL:         {OP_ROLL, "ROLL", opRoll},
 259                 OP_ROT:          {OP_ROT, "ROT", opRot},
 260                 OP_SWAP:         {OP_SWAP, "SWAP", opSwap},
 261                 OP_TUCK:         {OP_TUCK, "TUCK", opTuck},
 262
 263                 OP_CAT:         {OP_CAT, "CAT", opCat},
 264                 OP_SUBSTR:      {OP_SUBSTR, "SUBSTR", opSubstr},
 265                 OP_LEFT:        {OP_LEFT, "LEFT", opLeft},
 266                 OP_RIGHT:       {OP_RIGHT, "RIGHT", opRight},
 267                 OP_SIZE:        {OP_SIZE, "SIZE", opSize},
 268                 OP_CATPUSHDATA: {OP_CATPUSHDATA, "CATPUSHDATA", opCatpushdata},
 269
 270                 OP_INVERT:      {OP_INVERT, "INVERT", opInvert},
 271                 OP_AND:         {OP_AND, "AND", opAnd},
 272                 OP_OR:          {OP_OR, "OR", opOr},
 273                 OP_XOR:         {OP_XOR, "XOR", opXor},
 274                 OP_EQUAL:       {OP_EQUAL, "EQUAL", opEqual},
 275                 OP_EQUALVERIFY: {OP_EQUALVERIFY, "EQUALVERIFY", opEqualVerify},
 276
 277                 OP_1ADD:               {OP_1ADD, "1ADD", op1Add},
 278                 OP_1SUB:               {OP_1SUB, "1SUB", op1Sub},
 279                 OP_2MUL:               {OP_2MUL, "2MUL", op2Mul},
 280                 OP_2DIV:               {OP_2DIV, "2DIV", op2Div},
 281                 OP_NEGATE:             {OP_NEGATE, "NEGATE", opNegate},
 282                 OP_ABS:                {OP_ABS, "ABS", opAbs},
 283                 OP_NOT:                {OP_NOT, "NOT", opNot},
 284                 OP_0NOTEQUAL:          {OP_0NOTEQUAL, "0NOTEQUAL", op0NotEqual},
 285                 OP_ADD:                {OP_ADD, "ADD", opAdd},
 286                 OP_SUB:                {OP_SUB, "SUB", opSub},
 287                 OP_MUL:                {OP_MUL, "MUL", opMul},
 288                 OP_DIV:                {OP_DIV, "DIV", opDiv},
 289                 OP_MOD:                {OP_MOD, "MOD", opMod},
 290                 OP_LSHIFT:             {OP_LSHIFT, "LSHIFT", opLshift},
 291                 OP_RSHIFT:             {OP_RSHIFT, "RSHIFT", opRshift},
 292                 OP_BOOLAND:            {OP_BOOLAND, "BOOLAND", opBoolAnd},
 293                 OP_BOOLOR:             {OP_BOOLOR, "BOOLOR", opBoolOr},
 294                 OP_NUMEQUAL:           {OP_NUMEQUAL, "NUMEQUAL", opNumEqual},
 295                 OP_NUMEQUALVERIFY:     {OP_NUMEQUALVERIFY, "NUMEQUALVERIFY", opNumEqualVerify},
 296                 OP_NUMNOTEQUAL:        {OP_NUMNOTEQUAL, "NUMNOTEQUAL", opNumNotEqual},
 297                 OP_LESSTHAN:           {OP_LESSTHAN, "LESSTHAN", opLessThan},
 298                 OP_GREATERTHAN:        {OP_GREATERTHAN, "GREATERTHAN", opGreaterThan},
 299                 OP_LESSTHANOREQUAL:    {OP_LESSTHANOREQUAL, "LESSTHANOREQUAL", opLessThanOrEqual},
 300                 OP_GREATERTHANOREQUAL: {OP_GREATERTHANOREQUAL, "GREATERTHANOREQUAL", opGreaterThanOrEqual},
 301                 OP_MIN:                {OP_MIN, "MIN", opMin},
 302                 OP_MAX:                {OP_MAX, "MAX", opMax},
 303                 OP_WITHIN:             {OP_WITHIN, "WITHIN", opWithin},
 304                 OP_MULFRACTION:        {OP_MULFRACTION, "MULFRACTION", opMulFraction},
 305
 306                 OP_SHA256:        {OP_SHA256, "SHA256", opSha256},
 307                 OP_SHA3:          {OP_SHA3, "SHA3", opSha3},
 308                 OP_HASH160:       {OP_HASH160, "HASH160", opHash160},
 309                 OP_CHECKSIG:      {OP_CHECKSIG, "CHECKSIG", opCheckSig},
 310                 OP_CHECKMULTISIG: {OP_CHECKMULTISIG, "CHECKMULTISIG", opCheckMultiSig},
 311                 OP_TXSIGHASH:     {OP_TXSIGHASH, "TXSIGHASH", opTxSigHash},
 312
 313                 OP_CHECKOUTPUT: {OP_CHECKOUTPUT, "CHECKOUTPUT", opCheckOutput},
 314                 OP_ASSET:       {OP_ASSET, "ASSET", opAsset},
 315                 OP_AMOUNT:      {OP_AMOUNT, "AMOUNT", opAmount},
 316                 OP_PROGRAM:     {OP_PROGRAM, "PROGRAM", opProgram},
 317                 OP_INDEX:       {OP_INDEX, "INDEX", opIndex},
 318                 OP_ENTRYID:     {OP_ENTRYID, "ENTRYID", opEntryID},
 319                 OP_OUTPUTID:    {OP_OUTPUTID, "OUTPUTID", opOutputID},
 320                 OP_BLOCKHEIGHT: {OP_BLOCKHEIGHT, "BLOCKHEIGHT", opBlockHeight},
 321         }
 322
 323         opsByName map[string]opInfo
 324 )
 325
 326 // ParseOp parses the op at position pc in prog, returning the parsed
 327 // instruction (opcode plus any associated data).
 328 func ParseOp(prog []byte, pc uint32) (inst Instruction, err error) {
 329         if len(prog) > math.MaxInt32 {
 330                 err = ErrLongProgram
 331         }
 332         l := uint32(len(prog))
 333         if pc >= l {
 334                 err = ErrShortProgram
 335                 return
 336         }
 337         opcode := Op(prog[pc])
 338         inst.Op = opcode
 339         inst.Len = 1
 340         if opcode >= OP_1 && opcode <= OP_16 {
 341                 inst.Data = []byte{uint8(opcode-OP_1) + 1}
 342                 return
 343         }
 344         if opcode >= OP_DATA_1 && opcode <= OP_DATA_75 {
 345                 inst.Len += uint32(opcode - OP_DATA_1 + 1)
 346                 end, ok := checked.AddUint32(pc, inst.Len)
 347                 if !ok {
 348                         err = errors.WithDetail(checked.ErrOverflow, "data length exceeds max program size")
 349                         return
 350                 }
 351                 if end > l {
 352                         err = ErrShortProgram
 353                         return
 354                 }
 355                 inst.Data = prog[pc+1 : end]
 356                 return
 357         }
 358         if opcode == OP_PUSHDATA1 {
 359                 if pc == l-1 {
 360                         err = ErrShortProgram
 361                         return
 362                 }
 363                 n := prog[pc+1]
 364                 inst.Len += uint32(n) + 1
 365                 end, ok := checked.AddUint32(pc, inst.Len)
 366                 if !ok {
 367                         err = errors.WithDetail(checked.ErrOverflow, "data length exceeds max program size")
 368                 }
 369                 if end > l {
 370                         err = ErrShortProgram
 371                         return
 372                 }
 373                 inst.Data = prog[pc+2 : end]
 374                 return
 375         }
 376         if opcode == OP_PUSHDATA2 {
 377                 if len(prog) < 3 || pc > l-3 {
 378                         err = ErrShortProgram
 379                         return
 380                 }
 381                 n := binary.LittleEndian.Uint16(prog[pc+1 : pc+3])
 382                 inst.Len += uint32(n) + 2
 383                 end, ok := checked.AddUint32(pc, inst.Len)
 384                 if !ok {
 385                         err = errors.WithDetail(checked.ErrOverflow, "data length exceeds max program size")
 386                         return
 387                 }
 388                 if end > l {
 389                         err = ErrShortProgram
 390                         return
 391                 }
 392                 inst.Data = prog[pc+3 : end]
 393                 return
 394         }
 395         if opcode == OP_PUSHDATA4 {
 396                 if len(prog) < 5 || pc > l-5 {
 397                         err = ErrShortProgram
 398                         return
 399                 }
 400                 inst.Len += 4
 401
 402                 n := binary.LittleEndian.Uint32(prog[pc+1 : pc+5])
 403                 var ok bool
 404                 inst.Len, ok = checked.AddUint32(inst.Len, n)
 405                 if !ok {
 406                         err = errors.WithDetail(checked.ErrOverflow, "data length exceeds max program size")
 407                         return
 408                 }
 409                 end, ok := checked.AddUint32(pc, inst.Len)
 410                 if !ok {
 411                         err = errors.WithDetail(checked.ErrOverflow, "data length exceeds max program size")
 412                         return
 413                 }
 414                 if end > l {
 415                         err = ErrShortProgram
 416                         return
 417                 }
 418                 inst.Data = prog[pc+5 : end]
 419                 return
 420         }
 421         if opcode == OP_JUMP || opcode == OP_JUMPIF {
 422                 inst.Len += 4
 423                 end, ok := checked.AddUint32(pc, inst.Len)
 424                 if !ok {
 425                         err = errors.WithDetail(checked.ErrOverflow, "jump target exceeds max program size")
 426                         return
 427                 }
 428                 if end > l {
 429                         err = ErrShortProgram
 430                         return
 431                 }
 432                 inst.Data = prog[pc+1 : end]
 433                 return
 434         }
 435         return
 436 }
 437
 438 func ParseProgram(prog []byte) ([]Instruction, error) {
 439         var result []Instruction
 440         for pc := uint32(0); pc < uint32(len(prog)); { // update pc inside the loop
 441                 inst, err := ParseOp(prog, pc)
 442                 if err != nil {
 443                         return nil, err
 444                 }
 445                 result = append(result, inst)
 446                 var ok bool
 447                 pc, ok = checked.AddUint32(pc, inst.Len)
 448                 if !ok {
 449                         return nil, errors.WithDetail(checked.ErrOverflow, "program counter exceeds max program size")
 450                 }
 451         }
 452         return result, nil
 453 }
 454
 455 var isExpansion [256]bool
 456
 457 func init() {
 458         for i := 1; i <= 75; i++ {
 459                 ops[i] = opInfo{Op(i), fmt.Sprintf("DATA_%d", i), opPushdata}
 460         }
 461         for i := uint8(0); i <= 15; i++ {
 462                 op := uint8(OP_1) + i
 463                 ops[op] = opInfo{Op(op), fmt.Sprintf("%d", i+1), opPushdata}
 464         }
 465
 466         // This is here to break a dependency cycle
 467         ops[OP_CHECKPREDICATE] = opInfo{OP_CHECKPREDICATE, "CHECKPREDICATE", opCheckPredicate}
 468
 469         opsByName = make(map[string]opInfo)
 470         for _, info := range ops {
 471                 opsByName[info.name] = info
 472         }
 473         opsByName["0"] = ops[OP_FALSE]
 474         opsByName["TRUE"] = ops[OP_1]
 475
 476         for i := 0; i <= 255; i++ {
 477                 if ops[i].name == "" {
 478                         ops[i] = opInfo{Op(i), fmt.Sprintf("NOPx%02x", i), opNop}
 479                         isExpansion[i] = true
 480                 }
 481         }
 482 }
 483
 484 // IsPushdata judge instruction whether is a pushdata operation(include opFalse operation)
 485 func (inst *Instruction) IsPushdata() bool {
 486         if reflect.ValueOf(ops[inst.Op].fn) == reflect.ValueOf(ops[OP_1].fn) ||
 487                 reflect.ValueOf(ops[inst.Op].fn) == reflect.ValueOf(ops[OP_0].fn) {
 488                 return true
 489         }
 490
 491         return false
 492 }