Skip to content

Commit 07b6a3d

Browse files
committedJul 22, 2018
Tighten Int.to bounds and add twos-complement bitcount
·
0.15.10.3.0
1 parent bbd2933 commit 07b6a3d

File tree

1 file changed

+91
-12
lines changed

1 file changed

+91
-12
lines changed
 

‎std/math/big/int.zig‎

Lines changed: 91 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -115,13 +115,47 @@ pub const Int = struct {
115115
return !r.isOdd();
116116
}
117117

118-
fn bitcount(self: Int) usize {
119-
const u_bit_count = (self.len - 1) * Limb.bit_count + (Limb.bit_count - @clz(self.limbs[self.len - 1]));
120-
return usize(@boolToInt(!self.positive)) + u_bit_count;
118+
// Returns the number of bits required to represent the absolute value of self.
119+
fn bitCountAbs(self: Int) usize {
120+
return (self.len - 1) * Limb.bit_count + (Limb.bit_count - @clz(self.limbs[self.len - 1]));
121121
}
122122

123+
// Returns the number of bits required to represent the integer in twos-complement form.
124+
//
125+
// If the integer is negative the value returned is the number of bits needed by a signed
126+
// integer to represent the value. If positive the value is the number of bits for an
127+
// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
128+
// one greater than the returned value.
129+
//
130+
// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
131+
fn bitCountTwosComp(self: Int) usize {
132+
var bits = self.bitCountAbs();
133+
134+
// If the entire value has only one bit set (e.g. 0b100000000) then the negation in twos
135+
// complement requires one less bit.
136+
if (!self.positive) block: {
137+
bits += 1;
138+
139+
if (@popCount(self.limbs[self.len - 1]) == 1) {
140+
for (self.limbs[0 .. self.len - 1]) |limb| {
141+
if (@popCount(limb) != 0) {
142+
break :block;
143+
}
144+
}
145+
146+
bits -= 1;
147+
}
148+
}
149+
150+
return bits;
151+
}
152+
153+
// Returns the approximate size of the integer in the given base. Negative values accomodate for
154+
// the minus sign. This is used for determining the number of characters needed to print the
155+
// value. It is inexact and will exceed the given value by 1-2 digits.
123156
pub fn sizeInBase(self: Int, base: usize) usize {
124-
return (self.bitcount() / math.log2(base)) + 1;
157+
const bit_count = usize(@boolToInt(!self.positive)) + self.bitCountAbs();
158+
return (bit_count / math.log2(base)) + 1;
125159
}
126160

127161
pub fn set(self: *Int, value: var) Allocator.Error!void {
@@ -189,9 +223,9 @@ pub const Int = struct {
189223
pub fn to(self: Int, comptime T: type) ConvertError!T {
190224
switch (@typeId(T)) {
191225
TypeId.Int => {
192-
const UT = if (T.is_signed) @IntType(false, T.bit_count - 1) else T;
226+
const UT = @IntType(false, T.bit_count);
193227

194-
if (self.bitcount() > 8 * @sizeOf(UT)) {
228+
if (self.bitCountTwosComp() > T.bit_count) {
195229
return error.TargetTooSmall;
196230
}
197231

@@ -208,9 +242,17 @@ pub const Int = struct {
208242
}
209243

210244
if (!T.is_signed) {
211-
return if (self.positive) r else error.NegativeIntoUnsigned;
245+
return if (self.positive) @intCast(T, r) else error.NegativeIntoUnsigned;
212246
} else {
213-
return if (self.positive) @intCast(T, r) else -@intCast(T, r);
247+
if (self.positive) {
248+
return @intCast(T, r);
249+
} else {
250+
if (math.cast(T, r)) |ok| {
251+
return -ok;
252+
} else |_| {
253+
return @minValue(T);
254+
}
255+
}
214256
}
215257
},
216258
else => {
@@ -1120,24 +1162,61 @@ test "big.int bitcount + sizeInBase" {
11201162
var a = try Int.init(al);
11211163

11221164
try a.set(0b100);
1123-
debug.assert(a.bitcount() == 3);
1165+
debug.assert(a.bitCountAbs() == 3);
11241166
debug.assert(a.sizeInBase(2) >= 3);
11251167
debug.assert(a.sizeInBase(10) >= 1);
11261168

1169+
a.negate();
1170+
debug.assert(a.bitCountAbs() == 3);
1171+
debug.assert(a.sizeInBase(2) >= 4);
1172+
debug.assert(a.sizeInBase(10) >= 2);
1173+
11271174
try a.set(0xffffffff);
1128-
debug.assert(a.bitcount() == 32);
1175+
debug.assert(a.bitCountAbs() == 32);
11291176
debug.assert(a.sizeInBase(2) >= 32);
11301177
debug.assert(a.sizeInBase(10) >= 10);
11311178

11321179
try a.shiftLeft(a, 5000);
1133-
debug.assert(a.bitcount() == 5032);
1180+
debug.assert(a.bitCountAbs() == 5032);
11341181
debug.assert(a.sizeInBase(2) >= 5032);
11351182
a.positive = false;
11361183

1137-
debug.assert(a.bitcount() == 5033);
1184+
debug.assert(a.bitCountAbs() == 5032);
11381185
debug.assert(a.sizeInBase(2) >= 5033);
11391186
}
11401187

1188+
test "big.int bitcount/to" {
1189+
var a = try Int.init(al);
1190+
1191+
try a.set(0);
1192+
debug.assert(a.bitCountTwosComp() == 0);
1193+
1194+
// TODO: stack smashing
1195+
// debug.assert((try a.to(u0)) == 0);
1196+
// TODO: sigsegv
1197+
// debug.assert((try a.to(i0)) == 0);
1198+
1199+
try a.set(-1);
1200+
debug.assert(a.bitCountTwosComp() == 1);
1201+
debug.assert((try a.to(i1)) == -1);
1202+
1203+
try a.set(-8);
1204+
debug.assert(a.bitCountTwosComp() == 4);
1205+
debug.assert((try a.to(i4)) == -8);
1206+
1207+
try a.set(127);
1208+
debug.assert(a.bitCountTwosComp() == 7);
1209+
debug.assert((try a.to(u7)) == 127);
1210+
1211+
try a.set(-128);
1212+
debug.assert(a.bitCountTwosComp() == 8);
1213+
debug.assert((try a.to(i8)) == -128);
1214+
1215+
try a.set(-129);
1216+
debug.assert(a.bitCountTwosComp() == 9);
1217+
debug.assert((try a.to(i9)) == -129);
1218+
}
1219+
11411220
test "big.int string set" {
11421221
var a = try Int.init(al);
11431222
try a.setString(10, "120317241209124781241290847124");

0 commit comments

Comments
 (0)
Please sign in to comment.