2 * math64.h provides the 64 bit unsigned integer add, multiply followed by modulo operation
3 * The linux/math64.h provides divide and multiply 64 bit integers but:
4 * 1. multiply: mul_u64_u64_shr - only returns 64 bits of the result and has to be called
5 * twice to get the complete 128 bits of the result.
6 * 2. Modulo operation of the result of addition and multiplication of u64 that may result
7 * in integers > 64 bits is not supported
8 * Hence this header to combine add/multiply followed by modulo of u64 integrers
9 * always resulting in u64.
11 * Copyright (c) 2016 Cisco and/or its affiliates.
12 * Licensed under the Apache License, Version 2.0 (the "License");
13 * you may not use this file except in compliance with the License.
14 * You may obtain a copy of the License at:
16 * http://www.apache.org/licenses/LICENSE-2.0
18 * Unless required by applicable law or agreed to in writing, software
19 * distributed under the License is distributed on an "AS IS" BASIS,
20 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 * See the License for the specific language governing permissions and
22 * limitations under the License.
24 #ifndef include_vnet_math64_h
25 #define include_vnet_math64_h
29 * multiplies and returns result in hi and lo
31 static inline void mul64by64(u64 a, u64 b, u64 * hi, u64 * lo)
33 u64 a_lo = (u64) (uint32_t) a;
35 u64 b_lo = (u64) (u32) b;
43 u32 cy = (u32) (((p0 >> 32) + (u32) p1 + (u32) p2) >> 32);
45 *lo = p0 + (p1 << 32) + (p2 << 32);
46 *hi = p3 + (p1 >> 32) + (p2 >> 32) + cy;
50 #define TWO64 18446744073709551616.0
52 static inline u64 mod128by64(u64 x, u64 y, u64 m, double di)
58 /* calculate quotient first pass 53 bits */
59 dq = (TWO64 * (double)x + (double)y) * di;
62 q1 = 0xfffffffffffff800L;
66 /* q1 * m to compare the product to the dividend. */
67 mul64by64(q1, m, &p1, &p0);
69 /* Adjust quotient. is it > actual result: */
70 if (x < p1 || (x == p1 && y < p0))
72 /* q1 > quotient. calculate abs remainder */
73 x = p1 - (x + (p0 < y));
76 /* use the remainder as new dividend to adjust quotient */
77 q2 = (u64) ((TWO64 * (double)x + (double)y) * di);
78 mul64by64(q2, m, &p1, &p0);
81 if (x < p1 || (x == p1 && y <= p0))
94 x = x - (p1 + (y < p0));
97 q2 = (u64) ((TWO64 * (double)x + (double)y) * di);
98 mul64by64(q2, m, &p1, &p0);
101 if (x < p1 || (x == p1 && y < p0))
124 static inline u64 mod64by64(u64 a, u64 p, u64 primeinv)
126 return (mod128by64(0, a, p, primeinv));
129 static inline void add64(u64 a, u64 b, u64 * whi, u64 * wlo)
140 static inline u64 add64_mod(u64 a, u64 b, u64 p, double pi)
142 u64 shi = 0, slo = 0;
144 add64(a, b, &shi, &slo);
145 return (mod128by64(shi, slo, p, pi));
151 static inline u64 mul64_mod(u64 a, u64 b, u64 p, double pi)
153 u64 phi = 0, plo = 0;
155 mul64by64(a, b, &phi, &plo);
156 return (mod128by64(phi, plo, p, pi));