-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathshifts.fj
101 lines (83 loc) · 2.62 KB
/
shifts.fj
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
101
// ---------- Logical Shifts:
ns hex {
// Time Complexity: n(@+1)
// Space Complexity: n(@+28)
// dst[:n] <<= 1
def shl_bit n, dst {
.shifts.shl_bit_once dst+(n-1)*dw, 0
rep(n-1, i) .shifts.shl_bit_once dst+(n-2-i)*dw, dst+(n-1-i)*dw
}
// Time Complexity: n(@+1)
// Space Complexity: n(@+28)
// dst[:n] >>= 1
def shr_bit n, dst {
.shifts.shr_bit_once dst, 0
rep(n-1, i) .shifts.shr_bit_once dst+(i+1)*dw, dst+i*dw
}
// Time Complexity: n(@+4)
// Space Complexity: n(@+28)
// dst[:n] <<= 4
def shl_hex n, dst {
.shl_hex n, 1, dst
}
// Time Complexity: n(@+4)
// Space Complexity: n(@+28)
// dst[:n] <<= 4*times
def shl_hex n, times, dst @ end {
stl.comp_if0 times, end
.zero times, dst+(n-times)*dw
rep(n-times, i) .xor_zero dst+(n-1-i)*dw, dst+(n-1-times-i)*dw
end:
}
// Time Complexity: n(@+4)
// Space Complexity: n(@+28)
// dst[:n] >>= 4
def shr_hex n, dst {
.shr_hex n, 1, dst
}
// Time Complexity: n(@+4)
// Space Complexity: n(@+28)
// dst[:n] >>= 4*times
def shr_hex n, times, dst @ end {
stl.comp_if0 times, end
.zero times, dst
rep(n-times, i) .xor_zero dst+i*dw, dst+(i+times)*dw
end:
}
}
ns hex {
ns shifts {
// Time Complexity: @+1
// Space Complexity: @+28
// {next(1bit),dst(1hex)} = dst << 1
//
// next is the bit-address of the next msb, dst is a hex.
// @note, this should be called in reverse order (so that the "next" is already shifted).
def shl_bit_once dst, next @ switch, xor_by, end {
wflip dst+w, switch, dst
pad 16
switch:
rep(16, i) stl.fj i&8 ? next+dbit+0 : 0, xor_by+(i^((i<<1)&0xf))*dw
xor_by:
..tables.clean_table_entry__table 16, dst, end
end:
wflip dst+w, switch
}
// Time Complexity: @+1
// Space Complexity: @+28
// {next(1bit),dst(1hex)} = dst >> 1
//
// next is the bit-address of the next msb, dst is a hex.
// @note, this should be called in a regular order (so that the "next" is already shifted).
def shr_bit_once dst, next @ switch, xor_by, end {
wflip dst+w, switch, dst
pad 16
switch:
rep(16, i) stl.fj i&1 ? next+dbit+3 : 0, xor_by+(i^((i>>1)&0xf))*dw
xor_by:
..tables.clean_table_entry__table 16, dst, end
end:
wflip dst+w, switch
}
}
}