| 1 | |
| 2 |
|
| 3 |
|
| 4 | #include <linux/bits.h>
|
| 5 |
|
| 6 | #define T 32
|
| 7 | #include "cnum_defs.h"
|
| 8 | #undef T
|
| 9 |
|
| 10 | #define T 64
|
| 11 | #include "cnum_defs.h"
|
| 12 | #undef T
|
| 13 |
|
| 14 | struct cnum32 cnum32_from_cnum64(struct cnum64 cnum)
|
| 15 | {
|
| 16 | if (cnum64_is_empty(cnum))
|
| 17 | return CNUM32_EMPTY;
|
| 18 |
|
| 19 | if (cnum.size >= U32_MAX)
|
| 20 | return (struct cnum32){ .base = 0, .size = U32_MAX };
|
| 21 | else
|
| 22 | return (struct cnum32){ .base = (u32)cnum.base, .size = cnum.size };
|
| 23 | }
|
| 24 |
|
| 25 | |
| 26 | * Suppose 'a' and 'b' are laid out as follows:
|
| 27 | *
|
| 28 | * 64-bit number axis --->
|
| 29 | *
|
| 30 | * N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32
|
| 31 | * ||------|---|=====|-------||----------|=====|-------||----------|=====|----|--||
|
| 32 | * | |< b >| |< b >| |< b >| |
|
| 33 | * | | | |
|
| 34 | * |<--+--------------------------- a ---------------------------+--->|
|
| 35 | * | |
|
| 36 | * |<-------------------------- t -------------------------->|
|
| 37 | *
|
| 38 | * In such a case it is possible to infer a more tight representation t
|
| 39 | * such that ∀ v ∈ a, (u32)v ∈ b: v ∈ t.
|
| 40 |
|
| 41 | struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b)
|
| 42 | {
|
| 43 | |
| 44 | * To simplify reasoning, rotate the circles so that [virtual] a1 starts
|
| 45 | * at u32 boundary, b1 represents b in this new frame of reference.
|
| 46 |
|
| 47 | struct cnum32 b1 = { b.base - (u32)a.base, b.size };
|
| 48 | struct cnum64 t = a;
|
| 49 | u64 d, b1_max;
|
| 50 |
|
| 51 | if (cnum64_is_empty(a) || cnum32_is_empty(b))
|
| 52 | return CNUM64_EMPTY;
|
| 53 |
|
| 54 | if (cnum32_urange_overflow(b1)) {
|
| 55 | b1_max = (u32)b1.base + (u32)b1.size;
|
| 56 | if ((u32)a.size > b1_max && (u32)a.size < b1.base) {
|
| 57 | |
| 58 | * N*2^32 (N+1)*2^32
|
| 59 | * ||=====|------------|=====||=====|---------|---|=====||
|
| 60 | * |b1 ->| |<- b1||b1 ->| | |<- b1|
|
| 61 | * |<----------------- a1 ------------------>|
|
| 62 | * |<-------------- t ------------>|<-- d -->| (after adjustment)
|
| 63 | * ^
|
| 64 | * b1_max
|
| 65 |
|
| 66 | d = (u32)a.size - b1_max;
|
| 67 | t.size -= d;
|
| 68 | } else {
|
| 69 | |
| 70 | * No adjustments possible in the following cases:
|
| 71 | *
|
| 72 | * ||=====|------------|=====||===|=|-------------|=|===||
|
| 73 | * |b1 ->| |<- b1||b1 +>| |<+ b1|
|
| 74 | * |<----------------- a1 ------>| |
|
| 75 | * |<----------------- (or) a1 ------------------->|
|
| 76 |
|
| 77 | }
|
| 78 | } else {
|
| 79 | if (t.size < b1.base)
|
| 80 | |
| 81 | * N*2^32 (N+1)*2^32
|
| 82 | * ||----------|--|=======|--||------>
|
| 83 | * |<-- a1 -->| |<- b ->|
|
| 84 |
|
| 85 | return CNUM64_EMPTY;
|
| 86 | |
| 87 | * N*2^32 (N+1)*2^32
|
| 88 | * ||-------------|========|-||-----| -------|========|-||
|
| 89 | * | |<- b1 ->| | |<- b1 ->|
|
| 90 | * |<------------+ a1 ------------>|
|
| 91 | * |<------ t ------>| (after adjustment)
|
| 92 |
|
| 93 | t.base += b1.base;
|
| 94 | t.size -= b1.base;
|
| 95 | b1_max = b1.base + b1.size;
|
| 96 | d = 0;
|
| 97 | if ((u32)a.size < b1.base)
|
| 98 | |
| 99 | * N*2^32 (N+1)*2^32
|
| 100 | * ||-------------|========|-||------|-------|========|-||
|
| 101 | * | |<- b1 ->| | |<- b1 ->|
|
| 102 | * |<------------+-- a1 --+-------->|
|
| 103 | * |<- t ->|<-- d -->| (after adjustment)
|
| 104 |
|
| 105 | d = (u32)a.size + (BIT_ULL(32) - b1_max);
|
| 106 | else if ((u32)a.size >= b1_max)
|
| 107 | |
| 108 | * N*2^32 (N+1)*2^32
|
| 109 | * ||--|========|------------||--|========|-------|-----||
|
| 110 | * | |<- b1 ->| |<- b1 ->| |
|
| 111 | * |<-+------------------ a1 ------------+------>|
|
| 112 | * |<-------------- t --------------->|<- d ->| (after adjustment)
|
| 113 |
|
| 114 | d = (u32)a.size - b1_max;
|
| 115 | if (t.size < d)
|
| 116 | return CNUM64_EMPTY;
|
| 117 | t.size -= d;
|
| 118 | }
|
| 119 | return t;
|
| 120 | }
|