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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// SPDX-License-Identifier: GPL-2.0-only
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
#include <linux/bits.h>
#include <linux/bpf_verifier.h> /* for imod() */
#define T 32
#include "cnum_defs.h"
#undef T
#define T 64
#include "cnum_defs.h"
#undef T
struct cnum32 cnum32_from_cnum64(struct cnum64 cnum)
{
if (cnum64_is_empty(cnum))
return CNUM32_EMPTY;
if (cnum.size >= U32_MAX)
return (struct cnum32){ .base = 0, .size = U32_MAX };
else
return (struct cnum32){ .base = (u32)cnum.base, .size = cnum.size };
}
/*
* Suppose 'a' and 'b' are laid out as follows:
*
* 64-bit number axis --->
*
* N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32
* ||------|---|=====|-------||----------|=====|-------||----------|=====|----|--||
* | |< b >| |< b >| |< b >| |
* | | | |
* |<--+--------------------------- a ---------------------------+--->|
* | |
* |<-------------------------- t -------------------------->|
*
* In such a case it is possible to infer a more tight representation t
* such that ∀ v ∈ a, (u32)v ∈ b: v ∈ t.
*/
struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b)
{
/*
* To simplify reasoning, rotate the circles so that [virtual] a1 starts
* at u32 boundary, b1 represents b in this new frame of reference.
*/
struct cnum32 b1 = { b.base - (u32)a.base, b.size };
struct cnum64 t = a;
u64 d, b1_max;
if (cnum64_is_empty(a) || cnum32_is_empty(b))
return CNUM64_EMPTY;
if (cnum32_urange_overflow(b1)) {
b1_max = (u32)b1.base + (u32)b1.size; /* overflow here is fine and necessary */
if ((u32)a.size > b1_max && (u32)a.size < b1.base) {
/*
* N*2^32 (N+1)*2^32
* ||=====|------------|=====||=====|---------|---|=====||
* |b1 ->| |<- b1||b1 ->| | |<- b1|
* |<----------------- a1 ------------------>|
* |<-------------- t ------------>|<-- d -->| (after adjustment)
* ^
* b1_max
*/
d = (u32)a.size - b1_max;
t.size -= d;
} else {
/*
* No adjustments possible in the following cases:
*
* ||=====|------------|=====||===|=|-------------|=|===||
* |b1 ->| |<- b1||b1 +>| |<+ b1|
* |<----------------- a1 ------>| |
* |<----------------- (or) a1 ------------------->|
*/
}
} else {
if (t.size < b1.base)
/*
* N*2^32 (N+1)*2^32
* ||----------|--|=======|--||------>
* |<-- a1 -->| |<- b ->|
*/
return CNUM64_EMPTY;
/*
* N*2^32 (N+1)*2^32
* ||-------------|========|-||-----| -------|========|-||
* | |<- b1 ->| | |<- b1 ->|
* |<------------+ a1 ------------>|
* |<------ t ------>| (after adjustment)
*/
t.base += b1.base;
t.size -= b1.base;
b1_max = b1.base + b1.size;
d = 0;
if ((u32)a.size < b1.base)
/*
* N*2^32 (N+1)*2^32
* ||-------------|========|-||------|-------|========|-||
* | |<- b1 ->| | |<- b1 ->|
* |<------------+-- a1 --+-------->|
* |<- t ->|<-- d -->| (after adjustment)
*/
d = (u32)a.size + (BIT_ULL(32) - b1_max);
else if ((u32)a.size >= b1_max)
/*
* N*2^32 (N+1)*2^32
* ||--|========|------------||--|========|-------|-----||
* | |<- b1 ->| |<- b1 ->| |
* |<-+------------------ a1 ------------+------>|
* |<-------------- t --------------->|<- d ->| (after adjustment)
*/
d = (u32)a.size - b1_max;
if (t.size < d)
return CNUM64_EMPTY;
t.size -= d;
}
return t;
}
/* Intersect 'in' with the set of integers defined by equation 'base + step * k'. */
struct cnum64 cnum64_intersect_linear(struct cnum64 in, u16 base, u16 step)
{
s64 smin = cnum64_smin(in);
s64 smax = cnum64_smax(in);
s64 lo, hi;
u16 d;
if (step <= 1 || cnum64_is_empty(in) || cnum64_srange_overflow(in))
return in;
/*
* Round smin up to the next value congruent to 'base' modulo 'step',
* i.e. increase smin by d = (base - smin) mod step:
*
* |<---- d ---->|
* |-----------|=============|...
* base+step*k smin base+step*(k+1)
*/
d = imod(base - imod(smin, step), step);
if ((u64)smax - (u64)smin < d)
return CNUM64_EMPTY;
lo = smin + d;
/*
* Round smax down to the previous value congruent to 'base' modulo 'step',
* i.e. decrease smax by d = (smax - base) mod step:
*
* |<--- d --->|
* ...|===========|-------------|
* base+step*k smax base+step*(k+1)
*/
d = imod(imod(smax, step) - base, step);
hi = smax - d;
return cnum64_from_srange(lo, hi);
}
|
