blocks.gno
6.30 Kb · 216 lines
1// Package blocks encodes a radio rotation, an ordered list of slots (an id
2// and a duration), as strings the caller stores under its own keys: a header
3// (slot count, total, one total per group), one group string per Size² slots
4// (one sum per block) and one block string per Size slots. Appending is O(1),
5// changing a slot rewrites one block, one group and the header, and finding
6// the slot at a position in the loop scans the group totals, one group's sums
7// and a single block: O(n/Size² + Size), flat up to about two million slots.
8// Inside a block, ids and durations are packed as fixed-width base-64 digits
9// (4 per id, 2 per duration): 6 bytes of deposit per slot.
10package blocks
11
12import "gno.land/p/nym-alexiscolin000/gnoradio/store/v0"
13
14// Size is the number of slots per block.
15const Size = 128
16
17// MaxID and MaxDur are what the packed digits hold.
18const (
19 MaxID = 1<<24 - 1 // 16,777,215
20 MaxDur = 1<<12 - 1 // 4095 seconds
21)
22
23func checkSlot(id int, dur int64) {
24 if id < 0 || id > MaxID {
25 panic("blocks: id out of range")
26 }
27 if dur < 0 || dur > MaxDur {
28 panic("blocks: duration out of range")
29 }
30}
31
32const groupSlots = Size * Size // slots per group
33
34// ---- Codec form: the same rotation over strings the caller stores ----
35//
36// A rotation is a header (slot count, total, one total per group), one group
37// string per Size² slots (one sum per block) and one block string per Size
38// slots (an id and a duration per slot). The caller keeps them under its own
39// keys; Where names the group and block of a slot. Each function takes the
40// strings one call touches and returns them updated, so a write costs the
41// header, one group and one block whatever the length.
42
43// MaxSlots is the longest rotation a header counts.
44const MaxSlots = 1<<24 - 1
45
46// Widths in base-64 digits.
47const (
48 nW = 4 // header: slot count
49 totW = 6 // header: total, then each group's total
50 sumW = 4 // group: one block's sum
51 slotW = 6 // block: id (4) and duration (2)
52)
53
54// add adds d to the number of width w at position at of s.
55func add(s string, at, w int, d int64) string {
56 return s[:at] + store.Fixed(store.Num(s, at, w)+d, w) + s[at+w:]
57}
58
59// Len is the number of slots of a rotation ("" is empty).
60func Len(h string) int {
61 if h == "" {
62 return 0
63 }
64 return int(store.Num(h, 0, nW))
65}
66
67// Total is the sum of all durations.
68func Total(h string) int64 {
69 if h == "" {
70 return 0
71 }
72 return store.Num(h, nW, totW)
73}
74
75// Where returns the group and block (counted from the start of the
76// rotation) that hold slot i.
77func Where(i int) (g, b int) { return i / groupSlots, i / Size }
78
79// fit panics unless grp and blk are slot i's group and block in a rotation
80// of n slots (i == n: where the next slot goes, "" when new).
81func fit(n int, grp, blk string, i int) {
82 g, b := Where(i)
83 inG, inB := clamp(n-g*groupSlots, groupSlots), clamp(n-b*Size, Size)
84 if len(grp) != (inG+Size-1)/Size*sumW || len(blk) != inB*slotW {
85 panic("blocks: wrong group or block for this slot")
86 }
87}
88
89func clamp(v, max int) int {
90 if v < 0 {
91 return 0
92 }
93 if v > max {
94 return max
95 }
96 return v
97}
98
99// Slot returns the id and duration of slot i, from its block.
100func Slot(blk string, i int) (int, int64) {
101 k := i % Size
102 if i < 0 || len(blk) < (k+1)*slotW {
103 panic("blocks: index out of range")
104 }
105 return int(store.Num(blk, k*slotW, 4)), store.Num(blk, k*slotW+4, 2)
106}
107
108// Append adds a slot at the end. grp and blk are those of slot Len(h)
109// (Where), "" when it starts a new one. It returns the three strings and
110// the new slot's index.
111func Append(h, grp, blk string, id int, dur int64) (string, string, string, int) {
112 checkSlot(id, dur)
113 n := Len(h)
114 if n >= MaxSlots {
115 panic("blocks: rotation full")
116 }
117 fit(n, grp, blk, n)
118 if h == "" {
119 h = store.Fixed(0, nW) + store.Fixed(0, totW)
120 }
121 if n%groupSlots == 0 {
122 h += store.Fixed(0, totW)
123 }
124 if n%Size == 0 {
125 grp += store.Fixed(0, sumW)
126 }
127 g, b := Where(n)
128 blk += store.Fixed(int64(id), 4) + store.Fixed(dur, 2)
129 grp = add(grp, b%Size*sumW, sumW, dur)
130 h = add(add(add(h, 0, nW, 1), nW, totW, dur), nW+totW+g*totW, totW, dur)
131 return h, grp, blk, n
132}
133
134// Set replaces slot i's id and duration (0 takes it out of the loop).
135func Set(h, grp, blk string, i, id int, dur int64) (string, string, string) {
136 checkSlot(id, dur)
137 n := Len(h)
138 if i < 0 || i >= n {
139 panic("blocks: index out of range")
140 }
141 fit(n, grp, blk, i)
142 _, old := Slot(blk, i)
143 k := i % Size * slotW
144 blk = blk[:k] + store.Fixed(int64(id), 4) + store.Fixed(dur, 2) + blk[k+slotW:]
145 if d := dur - old; d != 0 {
146 g, b := Where(i)
147 grp = add(grp, b%Size*sumW, sumW, d)
148 h = add(add(h, nW, totW, d), nW+totW+g*totW, totW, d)
149 }
150 return h, grp, blk
151}
152
153// PrefixBefore returns the total duration of slots 0..i-1 (0 <= i <= Len).
154func PrefixBefore(h, grp, blk string, i int) int64 {
155 n := Len(h)
156 if i < 0 || i > n {
157 panic("blocks: index out of range")
158 }
159 fit(n, grp, blk, i)
160 g, b := Where(i)
161 var p int64
162 for j := 0; j < g; j++ {
163 p += store.Num(h, nW+totW+j*totW, totW)
164 }
165 for j := 0; j < b%Size; j++ {
166 p += store.Num(grp, j*sumW, sumW)
167 }
168 for j := 0; j < i%Size; j++ {
169 p += store.Num(blk, j*slotW+4, 2)
170 }
171 return p
172}
173
174// Find is done in three steps, loading the group then the block between
175// them: FindGroup, FindBlock, FindSlot. FindGroup returns the group playing
176// at pos (0 <= pos < Total) and the position inside it; ok is false when pos
177// is out of range.
178func FindGroup(h string, pos int64) (g int, rest int64, ok bool) {
179 if pos < 0 || pos >= Total(h) {
180 return 0, 0, false
181 }
182 for at := nW + totW; at < len(h); at += totW {
183 t := store.Num(h, at, totW)
184 if pos < t {
185 return (at - nW - totW) / totW, pos, true
186 }
187 pos -= t
188 }
189 panic("blocks: bad header")
190}
191
192// FindBlock returns the block of group g playing at rest, and the position
193// inside it.
194func FindBlock(grp string, g int, rest int64) (b int, r int64) {
195 for j := 0; j*sumW < len(grp); j++ {
196 s := store.Num(grp, j*sumW, sumW)
197 if rest < s {
198 return g*Size + j, rest
199 }
200 rest -= s
201 }
202 panic("blocks: bad group")
203}
204
205// FindSlot returns the slot of block b playing at rest, its id and the
206// offset into it. Slots of duration 0 are never returned.
207func FindSlot(blk string, b int, rest int64) (slot, id int, offset int64) {
208 for k := 0; k*slotW < len(blk); k++ {
209 d := store.Num(blk, k*slotW+4, 2)
210 if rest < d {
211 return b*Size + k, int(store.Num(blk, k*slotW, 4)), rest
212 }
213 rest -= d
214 }
215 panic("blocks: bad block")
216}
