Ton

1
/*
2
    This file is part of TON Blockchain Library.
3

4
    TON Blockchain Library is free software: you can redistribute it and/or modify
5
    it under the terms of the GNU Lesser General Public License as published by
6
    the Free Software Foundation, either version 2 of the License, or
7
    (at your option) any later version.
8

9
    TON Blockchain Library is distributed in the hope that it will be useful,
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
    GNU Lesser General Public License for more details.
13

14
    You should have received a copy of the GNU Lesser General Public License
15
    along with TON Blockchain Library.  If not, see <http://www.gnu.org/licenses/>.
16

17
    Copyright 2017-2020 Telegram Systems LLP
18
*/
19
#include "func.h"
20

21
namespace funC {
22

23
/*
24
 * 
25
 *   GENERIC STACK TRANSFORMATIONS
26
 * 
27
 */
28

29
StackTransform::StackTransform(std::initializer_list<int> list) {
30
  *this = list;
31
}
32

33
StackTransform &StackTransform::operator=(std::initializer_list<int> list) {
34
  if (list.size() > 255) {
35
    invalidate();
36
    return *this;
37
  }
38
  set_id();
39
  if (!list.size()) {
40
    return *this;
41
  }
42
  int m = (int)list.size();
43
  d = list.begin()[m - 1] - (m - 1);
44
  if (d >= 128 || d < -128) {
45
    invalidate();
46
    return *this;
47
  }
48
  for (int i = 0; i < m - 1; i++) {
49
    int x = d + i;
50
    int y = list.begin()[i];
51
    if (y != x) {
52
      if (x != (short)x || y != (short)y || n == max_n) {
53
        invalidate();
54
        return *this;
55
      }
56
      dp = std::max(dp, std::max(x, y) + 1);
57
      A[n++] = std::make_pair((short)x, (short)y);
58
    }
59
  }
60
  return *this;
61
}
62

63
bool StackTransform::assign(const StackTransform &other) {
64
  if (!other.is_valid() || (unsigned)other.n > max_n) {
65
    return invalidate();
66
  }
67
  d = other.d;
68
  n = other.n;
69
  dp = other.dp;
70
  c = other.c;
71
  invalid = false;
72
  for (int i = 0; i < n; i++) {
73
    A[i] = other.A[i];
74
  }
75
  return true;
76
}
77

78
int StackTransform::get(int x) const {
79
  if (!is_valid()) {
80
    return -1;
81
  }
82
  if (x <= c_start) {
83
    return x - c;
84
  }
85
  x += d;
86
  int i;
87
  for (i = 0; i < n && A[i].first < x; i++) {
88
  }
89
  if (i < n && A[i].first == x) {
90
    return A[i].second;
91
  } else {
92
    return x;
93
  }
94
}
95

96
bool StackTransform::set(int x, int y, bool relaxed) {
97
  if (!is_valid()) {
98
    return false;
99
  }
100
  if (x < 0) {
101
    return (relaxed && y == x + d) || invalidate();
102
  }
103
  if (!relaxed) {
104
    touch(x);
105
  }
106
  x += d;
107
  int i;
108
  for (i = 0; i < n && A[i].first < x; i++) {
109
  }
110
  if (i < n && A[i].first == x) {
111
    if (x != y) {
112
      if (y != (short)y) {
113
        return invalidate();
114
      }
115
      A[i].second = (short)y;
116
    } else {
117
      --n;
118
      for (; i < n; i++) {
119
        A[i] = A[i + 1];
120
      }
121
    }
122
  } else {
123
    if (x != y) {
124
      if (x != (short)x || y != (short)y || n == max_n) {
125
        return invalidate();
126
      }
127
      for (int j = n++; j > i; j--) {
128
        A[j] = A[j - 1];
129
      }
130
      A[i].first = (short)x;
131
      A[i].second = (short)y;
132
      touch(x - d);
133
      touch(y);
134
    }
135
  }
136
  return true;
137
}
138

139
// f(x') = x' + d for all x' >= x ?
140
bool StackTransform::is_trivial_after(int x) const {
141
  return is_valid() && (!n || A[n - 1].first < x + d);
142
}
143

144
// card f^{-1}(y)
145
int StackTransform::preimage_count(int y) const {
146
  if (!is_valid()) {
147
    return -1;
148
  }
149
  int count = (y >= d);
150
  for (const auto &pair : A) {
151
    if (pair.second == y) {
152
      ++count;
153
    } else if (pair.first == y) {
154
      --count;
155
    }
156
  }
157
  return count;
158
}
159

160
// f^{-1}(y)
161
std::vector<int> StackTransform::preimage(int y) const {
162
  if (!is_valid()) {
163
    return {};
164
  }
165
  std::vector<int> res;
166
  bool f = (y >= d);
167
  for (const auto &pair : A) {
168
    if (pair.first > y && f) {
169
      res.push_back(y - d);
170
      f = false;
171
    }
172
    if (pair.first == y) {
173
      f = false;
174
    } else if (pair.second == y) {
175
      res.push_back(pair.first - d);
176
    }
177
  }
178
  return res;
179
}
180

181
// is f:N->N bijective ?
182
bool StackTransform::is_permutation() const {
183
  if (!is_valid() || d) {
184
    return false;
185
  }
186
  func_assert(n <= max_n);
187
  std::array<int, max_n> X, Y;
188
  for (int i = 0; i < n; i++) {
189
    X[i] = A[i].first;
190
    Y[i] = A[i].second;
191
    if (Y[i] < 0) {
192
      return false;
193
    }
194
  }
195
  std::sort(Y.begin(), Y.begin() + n);
196
  for (int i = 0; i < n; i++) {
197
    if (X[i] != Y[i]) {
198
      return false;
199
    }
200
  }
201
  return true;
202
}
203

204
bool StackTransform::remove_negative() {
205
  int s = 0;
206
  while (s < n && A[s].first < d) {
207
    ++s;
208
  }
209
  if (s) {
210
    n -= s;
211
    for (int i = 0; i < n; i++) {
212
      A[i] = A[i + s];
213
    }
214
  }
215
  return true;
216
}
217

218
int StackTransform::try_load(int &i, int offs) const {
219
  return i < n ? A[i++].first + offs : inf_x;
220
}
221

222
bool StackTransform::try_store(int x, int y) {
223
  if (x == y || x < d) {
224
    return true;
225
  }
226
  if (n == max_n || x != (short)x || y != (short)y) {
227
    return invalidate();
228
  }
229
  A[n].first = (short)x;
230
  A[n++].second = (short)y;
231
  return true;
232
}
233

234
// c := a * b
235
bool StackTransform::compose(const StackTransform &a, const StackTransform &b, StackTransform &c) {
236
  if (!a.is_valid() || !b.is_valid()) {
237
    return c.invalidate();
238
  }
239
  c.d = a.d + b.d;
240
  c.n = 0;
241
  c.dp = std::max(a.dp, b.dp + a.d);
242
  c.c = a.c + b.c;
243
  c.invalid = false;
244
  int i = 0, j = 0;
245
  int x1 = a.try_load(i);
246
  int x2 = b.try_load(j, a.d);
247
  while (true) {
248
    if (x1 < x2) {
249
      int y = a.A[i - 1].second;
250
      if (!c.try_store(x1, y)) {
251
        return false;
252
      }
253
      x1 = a.try_load(i);
254
    } else if (x2 < inf_x) {
255
      if (x1 == x2) {
256
        x1 = a.try_load(i);
257
      }
258
      int y = b.A[j - 1].second;
259
      if (!c.try_store(x2, a(y))) {
260
        return false;
261
      }
262
      x2 = b.try_load(j, a.d);
263
    } else {
264
      return true;
265
    }
266
  }
267
}
268

269
// this = this * other
270
bool StackTransform::apply(const StackTransform &other) {
271
  StackTransform res;
272
  if (!compose(*this, other, res)) {
273
    return invalidate();
274
  }
275
  return assign(res);
276
}
277

278
// this = other * this
279
bool StackTransform::preapply(const StackTransform &other) {
280
  StackTransform res;
281
  if (!compose(other, *this, res)) {
282
    return invalidate();
283
  }
284
  return assign(res);
285
}
286

287
StackTransform StackTransform::operator*(const StackTransform &b) const & {
288
  StackTransform res;
289
  compose(*this, b, res);
290
  return res;
291
}
292

293
// this = this * other
294
StackTransform &StackTransform::operator*=(const StackTransform &other) {
295
  StackTransform res;
296
  (compose(*this, other, res) && assign(res)) || invalidate();
297
  return *this;
298
}
299

300
bool StackTransform::apply_xchg(int i, int j, bool relaxed) {
301
  if (!is_valid() || i < 0 || j < 0) {
302
    return invalidate();
303
  }
304
  if (i == j) {
305
    return relaxed || touch(i);
306
  }
307
  int u = touch_get(i), v = touch_get(j);
308
  return set(i, v) && set(j, u);
309
}
310

311
bool StackTransform::apply_push(int i) {
312
  if (!is_valid() || i < 0) {
313
    return invalidate();
314
  }
315
  int u = touch_get(i);
316
  return shift(-1) && set(0, u);
317
}
318

319
bool StackTransform::apply_push_newconst() {
320
  if (!is_valid()) {
321
    return false;
322
  }
323
  return shift(-1) && set(0, c_start - c++);
324
}
325

326
bool StackTransform::apply_pop(int i) {
327
  if (!is_valid() || i < 0) {
328
    return invalidate();
329
  }
330
  if (!i) {
331
    return touch(0) && shift(1);
332
  } else {
333
    return set(i, get(0)) && shift(1);
334
  }
335
}
336

337
bool StackTransform::apply_blkpop(int k) {
338
  if (!is_valid() || k < 0) {
339
    return invalidate();
340
  }
341
  return !k || (touch(k - 1) && shift(k));
342
}
343

344
bool StackTransform::equal(const StackTransform &other, bool relaxed) const {
345
  if (!is_valid() || !other.is_valid()) {
346
    return false;
347
  }
348
  if (!(n == other.n && d == other.d)) {
349
    return false;
350
  }
351
  for (int i = 0; i < n; i++) {
352
    if (A[i] != other.A[i]) {
353
      return false;
354
    }
355
  }
356
  return relaxed || dp == other.dp;
357
}
358

359
StackTransform StackTransform::Xchg(int i, int j, bool relaxed) {
360
  StackTransform t;
361
  t.apply_xchg(i, j, relaxed);
362
  return t;
363
}
364

365
StackTransform StackTransform::Push(int i) {
366
  StackTransform t;
367
  t.apply_push(i);
368
  return t;
369
}
370

371
StackTransform StackTransform::Pop(int i) {
372
  StackTransform t;
373
  t.apply_pop(i);
374
  return t;
375
}
376

377
bool StackTransform::is_xchg(int i, int j) const {
378
  if (i == j) {
379
    return is_id();
380
  }
381
  return is_valid() && !d && n == 2 && i >= 0 && j >= 0 && get(i) == j && get(j) == i;
382
}
383

384
bool StackTransform::is_xchg(int *i, int *j) const {
385
  if (!is_valid() || d || n > 2 || !dp) {
386
    return false;
387
  }
388
  if (!n) {
389
    *i = *j = 0;
390
    return true;
391
  }
392
  if (n != 2) {
393
    return false;
394
  }
395
  int a = A[0].first, b = A[1].first;
396
  if (A[0].second != b || A[1].second != a) {
397
    return false;
398
  }
399
  *i = std::min(a, b);
400
  *j = std::max(a, b);
401
  return true;
402
}
403

404
bool StackTransform::is_xchg_xchg(int i, int j, int k, int l) const {
405
  if (is_valid() && !d && n <= 4 && (i | j | k | l) >= 0) {
406
    StackTransform t;
407
    return t.apply_xchg(i, j) && t.apply_xchg(k, l) && t <= *this;
408
  } else {
409
    return false;
410
  }
411
}
412

413
bool StackTransform::is_xchg_xchg(int *i, int *j, int *k, int *l) const {
414
  if (!is_valid() || d || n > 4 || !dp || !is_permutation()) {
415
    return false;
416
  }
417
  if (!n) {
418
    *i = *j = *k = *l = 0;
419
    return true;
420
  }
421
  if (n <= 2) {
422
    *k = *l = 0;
423
    return is_xchg(i, j);
424
  }
425
  if (n == 3) {
426
    // rotation: a -> b -> c -> a
427
    int a = A[0].first;
428
    int b = A[0].second;
429
    int s = (b == A[2].first ? 2 : 1);
430
    int c = A[s].second;
431
    if (b != A[s].first || c != A[3 - s].first || a != A[3 - s].second) {
432
      return false;
433
    }
434
    // implement as XCHG s(a),s(c) ; XCHG s(a),s(b)
435
    *i = *k = a;
436
    *j = c;
437
    *l = b;
438
    return is_xchg_xchg(*i, *j, *k, *l);
439
  }
440
  *i = A[0].first;
441
  *j = A[0].second;
442
  if (get(*j) != *i) {
443
    return false;
444
  }
445
  for (int s = 1; s < 4; s++) {
446
    if (A[s].first != *j) {
447
      *k = A[s].first;
448
      *l = A[s].second;
449
      return get(*l) == *k && is_xchg_xchg(*i, *j, *k, *l);
450
    }
451
  }
452
  return false;
453
}
454

455
bool StackTransform::is_push(int i) const {
456
  return is_valid() && d == -1 && n == 1 && A[0].first == -1 && A[0].second == i;
457
}
458

459
bool StackTransform::is_push(int *i) const {
460
  if (is_valid() && d == -1 && n == 1 && A[0].first == -1 && A[0].second >= 0) {
461
    *i = A[0].second;
462
    return true;
463
  } else {
464
    return false;
465
  }
466
}
467

468
// 1 2 3 4 .. = pop0
469
// 0 2 3 4 .. = pop1
470
// 1 0 3 4 .. = pop2
471
// 1 2 0 4 .. = pop3
472
// POP s(i) : 1 2 ... i-1 0 i+1 ... ; d=1, n=1, {(i,0)}
473
bool StackTransform::is_pop(int i) const {
474
  if (!is_valid() || d != 1 || n > 1 || i < 0) {
475
    return false;
476
  }
477
  if (!i) {
478
    return !n;
479
  }
480
  return n == 1 && A[0].first == i && !A[0].second;
481
}
482

483
bool StackTransform::is_pop(int *i) const {
484
  if (!is_valid() || d != 1 || n > 1) {
485
    return false;
486
  }
487
  if (!n) {
488
    *i = 0;
489
    return true;
490
  }
491
  if (n == 1 && !A[0].second) {
492
    *i = A[0].first;
493
    return true;
494
  }
495
  return false;
496
}
497

498
// POP s(i) ; POP s(j) : 2 ... i-1 0 i+1 ... j 1 j+2 ... ; d=2, n=2, {(i,0),(j+1,1)} if i <> j+1
499
bool StackTransform::is_pop_pop(int i, int j) const {
500
  if (is_valid() && d == 2 && n <= 2 && i >= 0 && j >= 0) {
501
    StackTransform t;
502
    return t.apply_pop(i) && t.apply_pop(j) && t <= *this;
503
  } else {
504
    return false;
505
  }
506
}
507

508
bool StackTransform::is_pop_pop(int *i, int *j) const {
509
  if (!is_valid() || d != 2 || n > 2) {
510
    return false;
511
  }
512
  if (!n) {
513
    *i = *j = 0;  // 2DROP
514
  } else if (n == 2) {
515
    *i = A[0].first - A[0].second;
516
    *j = A[1].first - A[1].second;
517
    if (A[0].second > A[1].second) {
518
      std::swap(*i, *j);
519
    }
520
  } else if (!A[0].second) {
521
    *i = A[0].first;
522
    *j = 0;
523
  } else {
524
    *i = 0;
525
    *j = A[0].first - 1;
526
  }
527
  return is_pop_pop(*i, *j);
528
}
529

530
const StackTransform StackTransform::rot{2, 0, 1, 3};
531
const StackTransform StackTransform::rot_rev{1, 2, 0, 3};
532

533
bool StackTransform::is_rot() const {
534
  return equal(rot, true);
535
}
536

537
bool StackTransform::is_rotrev() const {
538
  return equal(rot_rev, true);
539
}
540

541
// PUSH i ; ROT == 1 i 0 2 3
542
bool StackTransform::is_push_rot(int i) const {
543
  return is_valid() && d == -1 && i >= 0 && is_trivial_after(3) && get(0) == 1 && get(1) == i && get(2) == 0;
544
}
545

546
bool StackTransform::is_push_rot(int *i) const {
547
  return is_valid() && (*i = get(1)) >= 0 && is_push_rot(*i);
548
}
549

550
// PUSH i ; -ROT == 0 1 i 2 3
551
bool StackTransform::is_push_rotrev(int i) const {
552
  return is_valid() && d == -1 && i >= 0 && is_trivial_after(3) && get(0) == 0 && get(1) == 1 && get(2) == i;
553
}
554

555
bool StackTransform::is_push_rotrev(int *i) const {
556
  return is_valid() && (*i = get(2)) >= 0 && is_push_rotrev(*i);
557
}
558

559
// PUSH s(i) ; XCHG s(j),s(k) --> i 0 1 .. i ..
560
// PUSH s(i) ; XCHG s(0),s(k) --> k-1 0 1 .. k-2 i k ..
561
bool StackTransform::is_push_xchg(int i, int j, int k) const {
562
  StackTransform t;
563
  return is_valid() && d == -1 && n <= 3 && t.apply_push(i) && t.apply_xchg(j, k) && t <= *this;
564
}
565

566
bool StackTransform::is_push_xchg(int *i, int *j, int *k) const {
567
  if (!(is_valid() && d == -1 && n <= 3 && n > 0)) {
568
    return false;
569
  }
570
  int s = get(0);
571
  if (s < 0) {
572
    return false;
573
  }
574
  *i = s;
575
  *j = 0;
576
  if (n == 1) {
577
    *k = 0;
578
  } else if (n == 2) {
579
    *k = s + 1;
580
    *i = get(s + 1);
581
  } else {
582
    *j = A[1].first + 1;
583
    *k = A[2].first + 1;
584
  }
585
  return is_push_xchg(*i, *j, *k);
586
}
587

588
// XCHG s1,s(i) ; XCHG s0,s(j)
589
bool StackTransform::is_xchg2(int i, int j) const {
590
  StackTransform t;
591
  return is_valid() && !d && t.apply_xchg(1, i) && t.apply_xchg(0, j) && t <= *this;
592
}
593

594
bool StackTransform::is_xchg2(int *i, int *j) const {
595
  if (!is_valid() || d || n > 4 || n == 1 || dp < 2) {
596
    return false;
597
  }
598
  *i = get(1);
599
  *j = get(0);
600
  if (!n) {
601
    return true;
602
  }
603
  if (*i < 0 || *j < 0) {
604
    return false;
605
  }
606
  if (n == 2 && !*i) {
607
    *j = *i;  // XCHG s0,s1 = XCHG2 s0,s0
608
  } else if (n == 3 && *i) {
609
    // XCHG2 s(i),s(i) = XCHG s1,s(i) ; XCHG s0,s(i) : 0->1, 1->i
610
    *j = *i;
611
  }  // XCHG2 s0,s(i) = XCHG s0,s1 ; XCHG s0,s(i) : 0->i, 1->0
612
  return is_xchg2(*i, *j);
613
}
614

615
// XCHG s0,s(i) ; PUSH s(j)  = PUSH s(j') ; XCHG s1,s(i+1)
616
// j'=j if j!=0, j!=i
617
// j'=0 if j=i
618
// j'=i if j=0
619
bool StackTransform::is_xcpu(int i, int j) const {
620
  StackTransform t;
621
  return is_valid() && d == -1 && t.apply_xchg(0, i) && t.apply_push(j) && t <= *this;
622
}
623

624
bool StackTransform::is_xcpu(int *i, int *j) const {
625
  if (!is_valid() || d != -1 || n > 3 || dp < 1) {
626
    return false;
627
  }
628
  *i = get(1);
629
  *j = get(0);
630
  if (!*j) {
631
    *j = *i;
632
  } else if (*j == *i) {
633
    *j = 0;
634
  }
635
  return is_xcpu(*i, *j);
636
}
637

638
// PUSH s(i) ; XCHG s0, s1 ; XCHG s0, s(j+1)
639
bool StackTransform::is_puxc(int i, int j) const {
640
  StackTransform t;
641
  return is_valid() && d == -1 && t.apply_push(i) && t.apply_xchg(0, 1) && t.apply_xchg(0, j + 1) && t <= *this;
642
}
643

644
// j > 0 : 0 -> j, 1 -> i
645
// j = 0 : 0 -> i, 1 -> 0  ( PUSH s(i) )
646
// j = -1 : 0 -> 0, 1 -> i  ( PUSH s(i) ; XCHG s0, s1 )
647
bool StackTransform::is_puxc(int *i, int *j) const {
648
  if (!is_valid() || d != -1 || n > 3) {
649
    return false;
650
  }
651
  *i = get(1);
652
  *j = get(0);
653
  if (!*i && is_push(*j)) {
654
    std::swap(*i, *j);
655
    return is_puxc(*i, *j);
656
  }
657
  if (!*j) {
658
    --*j;
659
  }
660
  return is_puxc(*i, *j);
661
}
662

663
// PUSH s(i) ; PUSH s(j+1)
664
bool StackTransform::is_push2(int i, int j) const {
665
  StackTransform t;
666
  return is_valid() && d == -2 && t.apply_push(i) && t.apply_push(j + 1) && t <= *this;
667
}
668

669
bool StackTransform::is_push2(int *i, int *j) const {
670
  if (!is_valid() || d != -2 || n > 2) {
671
    return false;
672
  }
673
  *i = get(1);
674
  *j = get(0);
675
  return is_push2(*i, *j);
676
}
677

678
// XCHG s2,s(i) ; XCHG s1,s(j) ; XCHG s0,s(k)
679
bool StackTransform::is_xchg3(int *i, int *j, int *k) const {
680
  if (!is_valid() || d || dp < 3 || !is_permutation()) {
681
    return false;
682
  }
683
  for (int s = 2; s >= 0; s--) {
684
    *i = get(s);
685
    StackTransform t = Xchg(2, *i) * *this;
686
    if (t.is_xchg2(j, k)) {
687
      return true;
688
    }
689
  }
690
  return false;
691
}
692

693
// XCHG s1,s(i) ; XCHG s0,s(j) ; PUSH s(k)
694
bool StackTransform::is_xc2pu(int *i, int *j, int *k) const {
695
  if (!is_valid() || d != -1 || dp < 2) {
696
    return false;
697
  }
698
  for (int s = 2; s >= 1; s--) {
699
    *i = get(s);
700
    StackTransform t = Xchg(1, *i) * *this;
701
    if (t.is_xcpu(j, k)) {
702
      return true;
703
    }
704
  }
705
  return false;
706
}
707

708
// XCHG s1,s(i) ; PUSH s(j) ; XCHG s0,s1 ; XCHG s0,s(k+1)
709
bool StackTransform::is_xcpuxc(int *i, int *j, int *k) const {
710
  if (!is_valid() || d != -1 || dp < 2) {
711
    return false;
712
  }
713
  for (int s = 2; s >= 0; s--) {
714
    *i = get(s);
715
    StackTransform t = Xchg(1, *i) * *this;
716
    if (t.is_puxc(j, k)) {
717
      return true;
718
    }
719
  }
720
  return false;
721
}
722

723
// XCHG s0,s(i) ; PUSH s(j) ; PUSH s(k+1)
724
bool StackTransform::is_xcpu2(int *i, int *j, int *k) const {
725
  if (!is_valid() || d != -2 || dp < 1) {
726
    return false;
727
  }
728
  *i = get(2);
729
  StackTransform t = Xchg(0, *i) * *this;
730
  return t.is_push2(j, k);
731
}
732

733
// PUSH s(i) ; XCHG s0,s2 ; XCHG s1,s(j+1) ; XCHG s0,s(k+1)
734
// 0 -> i or 1 -> i or 2 -> i ; i has two preimages
735
// 0 -> k if k >= 2, k != j
736
// 1 -> j=k if j = k >= 2
737
// 1 -> j if j >= 2, k != 0
738
// 0 -> j if j >= 2, k = 0
739
// => i in {f(0), f(1), f(2)} ; j in {-1, 0, 1, f(0), f(1)} ; k in {-1, 0, 1, f(0), f(1)}
740
bool StackTransform::is_puxc2(int *i, int *j, int *k) const {
741
  if (!is_valid() || d != -1 || dp < 2) {
742
    return false;
743
  }
744
  for (int s = 2; s >= 0; s--) {
745
    *i = get(s);
746
    if (preimage_count(*i) != 2) {
747
      continue;
748
    }
749
    for (int u = -1; u <= 3; u++) {
750
      *j = (u >= 2 ? get(u - 2) : u);
751
      for (int v = -1; v <= 3; v++) {
752
        *k = (v >= 2 ? get(v - 2) : v);
753
        if (is_puxc2(*i, *j, *k)) {
754
          return true;
755
        }
756
      }
757
    }
758
  }
759
  return false;
760
}
761

762
// PUSH s(i) ; XCHG s0,s2 ; XCHG s1,s(j+1) ; XCHG s0,s(k+1)
763
bool StackTransform::is_puxc2(int i, int j, int k) const {
764
  StackTransform t;
765
  return is_valid() && d == -1 && dp >= 2          // basic checks
766
         && t.apply_push(i) && t.apply_xchg(0, 2)  // PUSH s(i) ; XCHG s0,s2
767
         && t.apply_xchg(1, j + 1)                 // XCHG s1,s(j+1)
768
         && t.apply_xchg(0, k + 1) && t <= *this;  // XCHG s0,s(k+2)
769
}
770

771
// PUSH s(i) ; XCHG s0,s1 ; XCHG s0,s(j+1) ; PUSH s(k+1)
772
bool StackTransform::is_puxcpu(int *i, int *j, int *k) const {
773
  if (!is_valid() || d != -2 || dp < 1) {
774
    return false;
775
  }
776
  StackTransform t = *this;
777
  if (t.apply_pop() && t.is_puxc(i, j)) {
778
    int y = get(0);
779
    auto v = t.preimage(y);
780
    if (!v.empty()) {
781
      *k = v[0] - 1;
782
      t.apply_push(*k + 1);
783
      return t <= *this;
784
    }
785
  }
786
  return false;
787
}
788

789
// PUSH s(i) ; XCHG s0,s1 ; PUSH s(j+1) ; XCHG s0,s1 ; XCHG s0,s(k+2)
790
// 2 -> i;  1 -> j (if j >= 1, k != -1), 1 -> i (if j = 0, k != -1), 1 -> 0 (if j = -1, k != -1)
791
// 0 -> k (if k >= 1), 0 -> i (if k = 0), 0 -> j (if k = -1, j >= 1)
792
bool StackTransform::is_pu2xc(int *i, int *j, int *k) const {
793
  if (!is_valid() || d != -2 || dp < 1) {
794
    return false;
795
  }
796
  *i = get(2);
797
  for (int v = -2; v <= 1; v++) {
798
    *k = (v <= 0 ? v : get(0));  // one of -2, -1, 0, get(0)
799
    for (int u = -1; u <= 1; u++) {
800
      *j = (u <= 0 ? u : get(v != -1));  // one of -1, 0, get(0), get(1)
801
      if (is_pu2xc(*i, *j, *k)) {
802
        return true;
803
      }
804
    }
805
  }
806
  return false;
807
}
808

809
bool StackTransform::is_pu2xc(int i, int j, int k) const {
810
  StackTransform t;
811
  return is_valid() && d == -2 && dp >= 1              // basic checks
812
         && t.apply_push(i) && t.apply_xchg(0, 1)      // PUSH s(i) ; XCHG s0,s1
813
         && t.apply_push(j + 1) && t.apply_xchg(0, 1)  // PUSH s(j+1) ; XCHG s0,s1
814
         && t.apply_xchg(0, k + 2) && t <= *this;      // XCHG s0,s(k+2)
815
}
816

817
// PUSH s(i) ; PUSH s(j+1) ; PUSH s(k+2)
818
bool StackTransform::is_push3(int i, int j, int k) const {
819
  StackTransform t;
820
  return is_valid() && d == -3 && t.apply_push(i) && t.apply_push(j + 1) && t.apply_push(k + 2) && t <= *this;
821
}
822

823
bool StackTransform::is_push3(int *i, int *j, int *k) const {
824
  if (!is_valid() || d != -3 || n > 3) {
825
    return false;
826
  }
827
  *i = get(2);
828
  *j = get(1);
829
  *k = get(0);
830
  return is_push3(*i, *j, *k);
831
}
832

833
bool StackTransform::is_blkswap(int *i, int *j) const {
834
  if (!is_valid() || d || !is_permutation()) {
835
    return false;
836
  }
837
  *j = get(0);
838
  if (*j <= 0) {
839
    return false;
840
  }
841
  auto v = preimage(0);
842
  if (v.size() != 1) {
843
    return false;
844
  }
845
  *i = v[0];
846
  return *i > 0 && is_blkswap(*i, *j);
847
}
848

849
bool StackTransform::is_blkswap(int i, int j) const {
850
  if (!is_valid() || d || i <= 0 || j <= 0 || dp < i + j || !is_trivial_after(i + j)) {
851
    return false;
852
  }
853
  for (int s = 0; s < i; s++) {
854
    if (get(s) != s + j) {
855
      return false;
856
    }
857
  }
858
  for (int s = 0; s < j; s++) {
859
    if (get(s + i) != s) {
860
      return false;
861
    }
862
  }
863
  return true;
864
}
865

866
// equivalent to i times DROP
867
bool StackTransform::is_blkdrop(int *i) const {
868
  if (is_valid() && d > 0 && !n) {
869
    *i = d;
870
    return true;
871
  }
872
  return false;
873
}
874

875
// 0 1 .. j-1 j+i j+i+1 ...
876
bool StackTransform::is_blkdrop2(int i, int j) const {
877
  if (!is_valid() || d != i || i <= 0 || j < 0 || dp < i + j || n != j || !is_trivial_after(j)) {
878
    return false;
879
  }
880
  for (int s = 0; s < j; s++) {
881
    if (get(s) != s) {
882
      return false;
883
    }
884
  }
885
  return true;
886
}
887

888
bool StackTransform::is_blkdrop2(int *i, int *j) const {
889
  if (is_valid() && is_blkdrop2(d, n)) {
890
    *i = d;
891
    *j = n;
892
    return true;
893
  }
894
  return false;
895
}
896

897
// equivalent to i times PUSH s(j)
898
bool StackTransform::is_blkpush(int *i, int *j) const {
899
  if (!is_valid() || d >= 0) {
900
    return false;
901
  }
902
  *i = -d;
903
  *j = get(*i - 1);
904
  return is_blkpush(*i, *j);
905
}
906

907
bool StackTransform::is_blkpush(int i, int j) const {
908
  if (!is_valid() || d >= 0 || d != -i || j < 0 || dp < i + j || !is_trivial_after(i)) {
909
    return false;
910
  }
911
  StackTransform t;
912
  for (int s = 0; s < i; s++) {
913
    if (!t.apply_push(j)) {
914
      return false;
915
    }
916
  }
917
  return t <= *this;
918
}
919

920
bool StackTransform::is_reverse(int *i, int *j) const {
921
  if (!is_valid() || d || !is_permutation() || n < 2) {
922
    return false;
923
  }
924
  *j = A[0].first;
925
  *i = A[n - 1].first - A[0].first + 1;
926
  return is_reverse(*i, *j);
927
}
928

929
bool StackTransform::is_reverse(int i, int j) const {
930
  if (!is_valid() || d || !is_trivial_after(i + j) || n < 2 || A[0].first != j || A[n - 1].first != j + i - 1) {
931
    return false;
932
  }
933
  for (int s = 0; s < i; s++) {
934
    if (get(j + s) != j + i - 1 - s) {
935
      return false;
936
    }
937
  }
938
  return true;
939
}
940

941
// 0 i+1 i+2 ... == i*NIP
942
// j i+1 i+2 ... == XCHG s(i),s(j) ; BLKDROP i
943
bool StackTransform::is_nip_seq(int i, int j) const {
944
  return is_valid() && d == i && i > j && j >= 0 && n == 1 && A[0].first == i && A[0].second == j;
945
}
946

947
bool StackTransform::is_nip_seq(int *i) const {
948
  *i = d;
949
  return is_nip_seq(*i);
950
}
951

952
bool StackTransform::is_nip_seq(int *i, int *j) const {
953
  if (is_valid() && n > 0) {
954
    *i = d;
955
    *j = A[0].second;
956
    return is_nip_seq(*i, *j);
957
  } else {
958
    return false;
959
  }
960
}
961

962
// POP s(i); BLKDROP k  (usually for i >= k >= 0)
963
bool StackTransform::is_pop_blkdrop(int i, int k) const {
964
  StackTransform t;
965
  return is_valid() && d == k + 1 && t.apply_pop(i) && t.apply_blkpop(k) && t <= *this;
966
}
967

968
// POP s(i); BLKDROP k == XCHG s0,s(i); BLKDROP k+1  for i >= k >= 0
969
// k+1 k+2 .. i-1 0 i+1 ..
970
bool StackTransform::is_pop_blkdrop(int *i, int *k) const {
971
  if (is_valid() && n == 1 && d > 0 && !A[0].second) {
972
    *k = d - 1;
973
    *i = A[0].first;
974
    return is_pop_blkdrop(*i, *k);
975
  } else {
976
    return false;
977
  }
978
}
979

980
// POP s(i); POP s(j); BLKDROP k  (usually for i<>j >= k >= 0)
981
bool StackTransform::is_2pop_blkdrop(int i, int j, int k) const {
982
  StackTransform t;
983
  return is_valid() && d == k + 2 && t.apply_pop(i) && t.apply_pop(j) && t.apply_blkpop(k) && t <= *this;
984
}
985

986
// POP s(i); POP s(j); BLKDROP k == XCHG s0,s(i); XCHG s1,s(j+1); BLKDROP k+2 (usually for i<>j >= k >= 2)
987
// k+2 k+3 .. i-1 0 i+1 ... j 1 j+2 ...
988
bool StackTransform::is_2pop_blkdrop(int *i, int *j, int *k) const {
989
  if (is_valid() && n == 2 && d >= 2 && A[0].second + A[1].second == 1) {
990
    *k = d - 2;
991
    int t = (A[0].second > 0);
992
    *i = A[t].first;
993
    *j = A[1 - t].first - 1;
994
    return is_2pop_blkdrop(*i, *j, *k);
995
  } else {
996
    return false;
997
  }
998
}
999

1000
// PUSHCONST c ; ROT == 1 -1000 0 2 3
1001
bool StackTransform::is_const_rot(int c) const {
1002
  return is_valid() && d == -1 && is_trivial_after(3) && get(0) == 1 && c <= c_start && get(1) == c && get(2) == 0;
1003
}
1004

1005
bool StackTransform::is_const_rot(int *c) const {
1006
  return is_valid() && (*c = get(1)) <= c_start && is_const_rot(*c);
1007
}
1008

1009
// PUSHCONST c ; POP s(i) == 0 1 .. i-1 -1000 i+1 ...
1010
bool StackTransform::is_const_pop(int c, int i) const {
1011
  return is_valid() && !d && n == 1 && i > 0 && c <= c_start && get(i - 1) == c;
1012
}
1013

1014
bool StackTransform::is_const_pop(int *c, int *i) const {
1015
  if (is_valid() && !d && n == 1 && A[0].second <= c_start) {
1016
    *i = A[0].first + 1;
1017
    *c = A[0].second;
1018
    return is_const_pop(*c, *i);
1019
  } else {
1020
    return false;
1021
  }
1022
}
1023

1024
// PUSH i ; PUSHCONST c == c i 0 1 2 ...
1025
bool StackTransform::is_push_const(int i, int c) const {
1026
  return is_valid() && d == -2 && c <= c_start && i >= 0 && is_trivial_after(2) && get(0) == c && get(1) == i;
1027
}
1028

1029
bool StackTransform::is_push_const(int *i, int *c) const {
1030
  return is_valid() && d == -2 && n == 2 && is_push_const(*i = get(1), *c = get(0));
1031
}
1032

1033
void StackTransform::show(std::ostream &os, int mode) const {
1034
  if (!is_valid()) {
1035
    os << "<invalid>";
1036
    return;
1037
  }
1038
  int mi = 0, ma = 0;
1039
  if (n > 0 && A[0].first < d) {
1040
    mi = A[0].first - d;
1041
  }
1042
  if (n > 0) {
1043
    ma = std::max(ma, A[n - 1].first - d + 1);
1044
  }
1045
  ma = std::max(ma + 1, dp - d);
1046
  os << '{';
1047
  if (dp == d) {
1048
    os << '|';
1049
  }
1050
  for (int i = mi; i < ma; i++) {
1051
    os << get(i) << (i == -1 ? '?' : (i == dp - d - 1 ? '|' : ' '));
1052
  }
1053
  os << get(ma) << "..}";
1054
}
1055

1056
}  // namespace funC
1057