随想——Fish


字数统计: 3.6k字   |   阅读时长≈ 16分

这里的Fish不是shell的那个Fish，而是esolang的Fish（不是那个Fysh，是><>）

观前提示：你至少需要了解“后缀表达式”（或者“逆波兰表达式”）是什么

0. 简介

><>是一个基于栈的二维esolang，它的代码被放在一个二维的codebox中，且><>程序都是从左上角(0,0)开始运行的，如果指针超出了codebox的范围，那么它就会“跳”到另一侧

感觉就像一条🐟在池塘里面游来游去的，但是这个池塘上下左右带传送门（笑）

1. 基础命令

1.1 箭头

我们的🐟没啥想法，只会一味地往前游，除非你让它拐个弯

我们的🐟一开始是向右游，并且会一直往同一个方向游，如果需要改变方向，则需要这四个指令更改🐟游动的方向：^，v，<，>

非常形象有没有，遇到哪个箭头就变更方向往对应的方向游动

1.2 镜子

我们的🐟非常轴，它不撞南墙不回头

镜子也是一个用于变更方向的指令，包括/，\，|，_和#

玩过某开放大世界游戏的了解过镜面反射的同学们应该都能很快理解/和\是怎么一回事，实际上就是（右&上/左&下）互换和（左&上/右&下）互换

|和_就是180°变更方向，当然仅限于垂直入射游的🐟，如果是平行线（比如往下游时遇到了|）那么它就没有效果

#则是|和_放在一起，只要碰到就是180°变更方向

在讲更多的移动之前，我们先来讲讲一些基础运算和栈

1.3 基础值和基础运算

我们的🐟会将路上遇到的所有东西吃进去，需要的时候会按照时间先后将东西吐出来进行操作

对于><>，0123456789abcdef就是基础值，分别表示0~15的一个值，遇到了就会将这个值压入栈里

接下来就是+-*/%这五种基础的运算，就是加减乘除和求余，对于这五种运算符（暂时记为op），假如我们此时有如下的栈空间：

1
2
(stack bottom) -> (stack top)
x y z

接下来要执行op，则弹出栈顶的两个元素（这里是y和z），并执行y op z再将结果压入栈

比如遇到的是-，则完成指令后栈空间是这样的：

1
2
(stack bottom) -> (stack top)
x y-z

注意：这里的除法是浮点数除法

1.4 数值判断

除了🐟本身的运动，我们的🐟肚子也会因为吃进去的东西发生一些变化…

对于)(=这三个指令，分别表示大于，小于和等于，其操作类似上面的加减乘除，运算结果可以用如下的三元运算解释：

1
y op z ? 1 : 0

这里的z还是栈顶元素，y还是第二个元素

1.5 栈

有的时候我们的🐟吃进去了其它的🐟，而这些小🐟会在大🐟肚子里找吃的…

前面提到了><>是基于栈的，而这个语言的一大特色则是它可以创建任意多个栈

1.4 条件判断和其它移动

虽然🐟没有啥长期记忆，但是判断能力还是有的

有的时候，我们的🐟喝醉了，它也不知道往哪里游，这就是x的作用：随机变更方向

?. Fish逆向

为了这碟醋包了这桌饺子，憋憋

这里我们以InfobahnCTF 2025的逆向题fish为例，先看Fish代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
v
> 1:                  v
vv?(*******ffffffff:+1<      <p3+1+*43g44<
 >          :12345****1+%0=?v^            
         v+1%f:p44%5%d :$+@:<
         >::a%-0=?v9a*3-+                ^
                  >f1+3*+                ^
>~01+a*3+a*2+a*4+a*5+a*3+a*6+a*0+a*9+a*7+a*6v
v*a+8*a+8*a+8*a+4*a+3*a+5*a+8*a+2*a+1*a+5*a+<
>9+a*8+a*7+a*7+a*3+a*2+a*3+a*8+a*9+a*9+a*8+*v
v+0*a+7*a+5*a+3*a+6*a+9*a+8*a+8*a+1*a+6*a+10<
>a*3+a*6+a*6+a*6++>:f1+6*%84*+o0$v
          vv?(0-1: ~v?)0+1:-*+f16<
           ;        >        $1+$^
          >       ^

那么很明显，这个程序由2部分组成：上半部分和下半部分，理论上这个代码运行之后就能得到flag，但是光是第一个循环就要运行6个小时，还不清楚第2个循环要跑多久（实际上也要很长时间），因此还是让我们挨个部分分析吧：

上半部分：第一个循环

循环大致框架

这一部分我们需要分析的是下面的Fish：

1
2
3
4
5
6
7
v
> 1:                  v
vv?(*******ffffffff:+1<      <p3+1+*43g44<
 >          :12345****1+%0=?v^            
         v+1%f:p44%5%d :$+@:<
         >::a%-0=?v9a*3-+                ^
                  >f1+3*+                ^

可以分析出来上面的1:是在初始化栈空间，然后下面的蓝框和红框是主循环的两个分支，如果完成循环了就跳出整个循环进入下半部分的循环（也就是(0,2)的那个v）

先看蓝色框框，第2行那一串f和*实际上就是在计算0xF ** 8，然后和栈顶元素比较，如果小于等于栈顶元素就结束循环

第3行的12345****1+%0=?很明显是在判断栈顶元素是否能被121整除（(top) % 121 == 0 ? 1 : 0）

但是可能还是不够直观，那我们先简单走一遍循环看看栈空间是咋样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(stack bottom) -> (stack top)
1				; 1
1 1				; :
1 1 1			; 1
1 2				; +
1 2 2			; :
1 2 2 0xf**8	; ffffffff*******
1 2 1			; (  -> 2<0xf**8
1 2				; ? -> next code at (1,2)
1 2 2			; :
1 2 2 121		; 12345****1+
1 2 2			; %
1 2 2 0			; 0
1 2 0			; = -> 2!=0
1 2				; ? -> next code at (29,3), which is ^
1 2 1			; 1 -> code at (21,1), which is 1 at the start of the loop
1 3				; +
...				; continue loop...

可以看到我们每次循环后，栈顶元素就是循环的次数，从2开始，因此我们有如下的一个初步的框架代码：

1
2
3
4
5
for i in range(2,0xF**8):
	if i % 121 == 0:
		# do something
	else:
		continue

核心逻辑

那么我们知道了蓝色框在干什么，接下来就是分析剩下的红框了，让我们假设运行到栈顶空间元素为121…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
1 121			; ? -> next code at (28,3), which is v
1 121 121		; :
121 1 121		; @
121 122			; +
122 121			; $

122 121 121		; :
122 121 121 13	; d
122 121 4		; %
122 121 4		; 5%
122 121 4 4 4	; 44
122 121			; p -> save value 4 at (4,4)

122 121 2		; :f%1+ -> 121%15+1=2
122 121 2 1		; ::a%-0= -> 2-(2%0xA)==0
122 121	2		; ? -> next code at (18,5), which is v
122 121 50		; f1+3* -> +48

122 121 50 4 4	; 44
122 121 50 4	; g -> load previously saved value 4 at (4,4)
122 121 50 17 3	; 34*+1+3 -> 4+13
122 121			; p -> save value 50 at (17,3)

; continue blue block loop...

让我们首先看到上面栈空间的第15行，我们可以知道这里的2实际上就是循环数%5+1的结果

之后我们将会用lc表示循环数（Loop Count）

所以接下来就是在判断lc%5+1是否是大于10的，如果大于10就走上层逻辑9a*3-+（+87），否则就是这次循环中的f1+3*+（+48）

看到48（0x30）应该很快就能想到这里实际上就是在转ASCII，让0~15映射为对应的Hex字符，这里放87也是因为87+10=97（”a”）

但是这个字符要被放在哪里呢？我们能看到一开始（8~13行）计算了lc%d%5的值放在了(4,4)，而我们发现(4,4)不会被经过，因此可以看作是内存

接下来我们发现20~24行加载了(4,4)的值并加上了13，最后将ASCII放在了(lc%d%5+13, 3)的位置，因此就是放在(13,3)到(17,3)的其中某个地方

那么这5个槽在哪呢？数一数，发现就是上面的12345，所以每次进入红框循环就会修改下一次进入的条件，但是求连积这一点还是不会变的

因此我们可以单独把(13,3)到(17,3)的值拉出来作为一个数组，然后每次进入红框就更新数组并计算连积，至于值实际上就是0~15，不需要转ASCII，Fish代码里面转ASCII是为了能让Fish解释器正常读取运行

当然，每次进入红框循环的时候，栈底元素就会添加lc，因此最后可以有这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
from tqdm import tqdm

keys = [1,2,3,4,5]
sum_of_lc = 1
product = math.prod(keys)

for lc in tqdm(range(2,0xf ** 8)):
    if lc % (product+1) == 0:
        sum_of_lc += lc
        offset = (lc % 0xD) % 5
        rep = (lc % 0xF) + 1
        keys[offset] = rep
        product = math.prod(keys)
    else:
        continue
print(sum_of_lc)

大概运行十分钟就能跑出结果了，由此我们可以得到第一个循环结束后的栈空间是：

1
sum_of_lc 0xF**8

下半部分：第二个循环

OK，现在我们已经知道第二个循环的初始栈空间是怎么样的了，接下来看看第二个循环路径是怎么样的：

我们可以看到一开始有个~弹出了栈顶元素（即lc），因此最后只有sum_of_lc保留了下来

除此之外，绝大部分的红色路径是只运行一次的，因此进入红青蓝三色循环路径的是一个经过预处理的sum_of_lc

之后用proc（Processed）表示预处理后的值

我们稍微模拟一下可以得到下面的栈空间过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
proc proc						; :
proc proc%96+32					; f1+6*%84*+
proc							; o -> print(chr(proc%96+32))
proc 0							; 0
0 proc							; $
0 proc-96						; 61f+*-
0 proc-96 proc-96				; :
0 proc-96 proc-95 0				; 1+0
0 proc-96 1						; ) -> proc-95>0
0 proc-96						; ? -> next code at (20,12), which is v
proc-96 0						; $
proc-96 1						; 1+
1 proc-96						; $
1 proc-96*2						; 61f+*-
...
proc//96 proc%96-96 proc%96-95	; last loop till :1+
proc//96 proc%96-96 0			; 0) -> proc%96-95<=0
proc//96 proc%96-96				; ? -> next code at (19,12), which is ~
proc//96						; ~
proc//96 proc//96-1				; :1-
proc//96 proc//96-1 0			; 0
proc//96 0						; ( -> proc//96-1>0
proc//96						; ? -> next code at (10,12)
proc//96 (proc//96)%96+32		; continue loop...
...

由此我们可以看出来就是不断输出chr(proc%96+32)，然后先判断proc//96<1是否成立，成立就结束程序，否则就让proc=proc//96继续循环

因此我们可以得到如下的代码：

1
2
3
4
5
6
while True:
    print(chr(proc%96+32),end="")
    nproc = proc//96
    if nproc < 1:
        break
    proc = nproc

这个就很快了，秒出

那么我们的proc怎么得到呢？实际上前面的红色路径就是一堆逆波兰表达式，我很懒，所以我直接让AI写了个求值程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def eval_postfix(expr: str, init_stack=None):
    """
    计算支持十六进制字面量的后缀表达式（无空格）。
    支持运算符: + - * / %
    """
    stack = list(init_stack) if init_stack else []

    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
        '%': lambda a, b: a % b,
    }

    i = 0
    while i < len(expr):
        ch = expr[i]

        # 如果是十六进制数字
        if ch.lower() in "0123456789abcdef":
            num = ch
            stack.append(int(num, 16))
            i+=1
            continue

        # 如果是运算符
        if ch in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[ch](a, b))
            i += 1
            continue

        raise ValueError(f"未知符号: {ch}")

    if len(stack) != 1:
        raise ValueError(f"表达式错误，栈最终内容: {stack}")
    return stack[0]


proc = eval_postfix("01+a*3+a*2+a*4+a*5+a*3+a*6+a*0+a*9+a*7+a*6+a*5+a*1+a*2+a*8+a*5+a*3+a*4+a*8+a*8+a*8+a*9+a*8+a*7+a*7+a*3+a*2+a*3+a*8+a*9+a*9+a*8+*01+a*6+a*1+a*8+a*8+a*9+a*6+a*3+a*5+a*7+a*0+a*3+a*6+a*6+a*6++", init_stack=[sum_of_lc])

当然，你也可以尝试用Fish解释器然后动调，在碰到:的时候输出栈顶就行了，第一个就是结果

因此最后我们集成一下代码就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import math
from tqdm import tqdm

def eval_postfix(expr: str, init_stack=None):
    """
    计算支持十六进制字面量的后缀表达式（无空格）。
    支持运算符: + - * / %
    """
    stack = list(init_stack) if init_stack else []

    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
        '%': lambda a, b: a % b,
    }

    i = 0
    while i < len(expr):
        ch = expr[i]

        # 如果是十六进制数字（支持多位）
        if ch.lower() in "0123456789abcdef":
            num = ch
            stack.append(int(num, 16))
            i+=1
            continue

        # 如果是运算符
        if ch in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[ch](a, b))
            i += 1
            continue

        raise ValueError(f"未知符号: {ch}")

    if len(stack) != 1:
        raise ValueError(f"表达式错误，栈最终内容: {stack}")
    return stack[0]


keys = [1,2,3,4,5]
sum_of_lc = 1
product = math.prod(keys)

for lc in tqdm(range(2,0xf ** 8)):
    if lc % (product+1) == 0:
        sum_of_lc += lc
        offset = (lc % 0xD) % 5
        rep = (lc % 0xF) + 1
        keys[offset] = rep
        product = math.prod(keys)
    else:
        continue
print(sum_of_lc)

proc = eval_postfix("01+a*3+a*2+a*4+a*5+a*3+a*6+a*0+a*9+a*7+a*6+a*5+a*1+a*2+a*8+a*5+a*3+a*4+a*8+a*8+a*8+a*9+a*8+a*7+a*7+a*3+a*2+a*3+a*8+a*9+a*9+a*8+*01+a*6+a*1+a*8+a*8+a*9+a*6+a*3+a*5+a*7+a*0+a*3+a*6+a*6+a*6++", init_stack=[sum_of_lc])

print(proc)
while True:
    print(chr(proc%96+32),end="")
    nproc = proc//96
    if nproc < 1:
        break
    proc = nproc

顺带一提：AI就是路边一条，烂完了，给我把x%f+1等价成x&0xF，闹麻了

附录：上半部分伪汇编

这一部分是我自己在分析程序的时候自己手搓的，因为做这题的时候也是第一次接触Fish，所以想着写成伪汇编会好看很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
push 1
dup     ; duplicate top of stack

LABEL1: 
push 1
add     ; (top+1) + (top)
dup
push f
push f
push f
push f
push f
push f
push f
push f
mul
mul
mul
mul
mul
mul
mul
lt      ; (top+1) < (top)
test
jz LABEL0
dup
push 1  ; (13,3)
push 2  ; (14,3)
push 3  ; (15,3)
push 4  ; (16,3)
push 5  ; (17,3)
mul
mul
mul
mul
push 1
add
mod     ; (top+1) % (top)
push 0
eq      ; (top+1) == (top)
test
jz LABEL1
dup
swap3       ; swap top 3 items of stack, e.g. (top) 4 3 2 1 -> (top) 3 2 4 1
add
swap2       ; swap top 2 items of stack
dup
push d
mod
push 5
mod
push 4
push 4
save        ; save offset at (4,4)
dup
push f
mod
push 1
add
dup
dup
push a
mod
sub     ; (top+1) - (top)
push 0
eq
test
jz LABEL2
push f
push 1
add
push 3
mul
add

LABEL3:
push 4
push 4
load    ; load offset at (4,4)
push 3
push 4
mul
add
push 1
add
push 3
save    ; change value at (value(4,4)+13, 3)
jmp LABEL1

LABEL2:
push 9
push a
mul
push 3
sub
add
jmp LABEL3

LABEL0:
; the next loop...

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一个喜欢睡觉的fw~~~