1 // SPDX-License-Identifier: GPL-2.0 2 3 #include <linux/bitops.h> 4 #include <linux/math.h> 5 #include <linux/string.h> 6 #include <asm/unaligned.h> 7 8 #ifdef CONFIG_VALGRIND 9 #include <valgrind/memcheck.h> 10 #endif 11 12 #include "varint.h" 13 14 /** 15 * bch2_varint_encode - encode a variable length integer 16 * @out: destination to encode to 17 * @v: unsigned integer to encode 18 * Returns: size in bytes of the encoded integer - at most 9 bytes 19 */ 20 int bch2_varint_encode(u8 *out, u64 v) 21 { 22 unsigned bits = fls64(v|1); 23 unsigned bytes = DIV_ROUND_UP(bits, 7); 24 __le64 v_le; 25 26 if (likely(bytes < 9)) { 27 v <<= bytes; 28 v |= ~(~0 << (bytes - 1)); 29 v_le = cpu_to_le64(v); 30 memcpy(out, &v_le, bytes); 31 } else { 32 *out++ = 255; 33 bytes = 9; 34 put_unaligned_le64(v, out); 35 } 36 37 return bytes; 38 } 39 40 /** 41 * bch2_varint_decode - encode a variable length integer 42 * @in: varint to decode 43 * @end: end of buffer to decode from 44 * @out: on success, decoded integer 45 * Returns: size in bytes of the decoded integer - or -1 on failure (would 46 * have read past the end of the buffer) 47 */ 48 int bch2_varint_decode(const u8 *in, const u8 *end, u64 *out) 49 { 50 unsigned bytes = likely(in < end) 51 ? ffz(*in & 255) + 1 52 : 1; 53 u64 v; 54 55 if (unlikely(in + bytes > end)) 56 return -1; 57 58 if (likely(bytes < 9)) { 59 __le64 v_le = 0; 60 61 memcpy(&v_le, in, bytes); 62 v = le64_to_cpu(v_le); 63 v >>= bytes; 64 } else { 65 v = get_unaligned_le64(++in); 66 } 67 68 *out = v; 69 return bytes; 70 } 71 72 /** 73 * bch2_varint_encode_fast - fast version of bch2_varint_encode 74 * @out: destination to encode to 75 * @v: unsigned integer to encode 76 * Returns: size in bytes of the encoded integer - at most 9 bytes 77 * 78 * This version assumes it's always safe to write 8 bytes to @out, even if the 79 * encoded integer would be smaller. 80 */ 81 int bch2_varint_encode_fast(u8 *out, u64 v) 82 { 83 unsigned bits = fls64(v|1); 84 unsigned bytes = DIV_ROUND_UP(bits, 7); 85 86 if (likely(bytes < 9)) { 87 v <<= bytes; 88 v |= ~(~0 << (bytes - 1)); 89 } else { 90 *out++ = 255; 91 bytes = 9; 92 } 93 94 put_unaligned_le64(v, out); 95 return bytes; 96 } 97 98 /** 99 * bch2_varint_decode_fast - fast version of bch2_varint_decode 100 * @in: varint to decode 101 * @end: end of buffer to decode from 102 * @out: on success, decoded integer 103 * Returns: size in bytes of the decoded integer - or -1 on failure (would 104 * have read past the end of the buffer) 105 * 106 * This version assumes that it is safe to read at most 8 bytes past the end of 107 * @end (we still return an error if the varint extends past @end). 108 */ 109 int bch2_varint_decode_fast(const u8 *in, const u8 *end, u64 *out) 110 { 111 #ifdef CONFIG_VALGRIND 112 VALGRIND_MAKE_MEM_DEFINED(in, 8); 113 #endif 114 u64 v = get_unaligned_le64(in); 115 unsigned bytes = ffz(*in) + 1; 116 117 if (unlikely(in + bytes > end)) 118 return -1; 119 120 if (likely(bytes < 9)) { 121 v >>= bytes; 122 v &= ~(~0ULL << (7 * bytes)); 123 } else { 124 v = get_unaligned_le64(++in); 125 } 126 127 *out = v; 128 return bytes; 129 } 130