Commit 17f14e1d65
Changed files (7)
lib
src
arch
wasm
test
behavior
lib/compiler_rt/bitreverse.zig
@@ -0,0 +1,65 @@
+const std = @import("std");
+const builtin = @import("builtin");
+const common = @import("common.zig");
+
+pub const panic = common.panic;
+
+comptime {
+ @export(__bitreversesi2, .{ .name = "__bitreversesi2", .linkage = common.linkage, .visibility = common.visibility });
+ @export(__bitreversedi2, .{ .name = "__bitreversedi2", .linkage = common.linkage, .visibility = common.visibility });
+ @export(__bitreverseti2, .{ .name = "__bitreverseti2", .linkage = common.linkage, .visibility = common.visibility });
+}
+
+inline fn bitreverseXi2(comptime T: type, a: T) T {
+ switch (@bitSizeOf(T)) {
+ 32 => {
+ var t: T = a;
+ t = ((t >> 1) & 0x55555555) | ((t & 0x55555555) << 1);
+ t = ((t >> 2) & 0x33333333) | ((t & 0x33333333) << 2);
+ t = ((t >> 4) & 0x0F0F0F0F) | ((t & 0x0F0F0F0F) << 4);
+ t = ((t >> 8) & 0x00FF00FF) | ((t & 0x00FF00FF) << 8);
+ t = (t >> 16) | (t << 16);
+ return t;
+ },
+ 64 => {
+ var t: T = a;
+ t = ((t >> 1) & 0x5555555555555555) | ((t & 0x5555555555555555) << 1);
+ t = ((t >> 2) & 0x3333333333333333) | ((t & 0x3333333333333333) << 2);
+ t = ((t >> 4) & 0x0F0F0F0F0F0F0F0F) | ((t & 0x0F0F0F0F0F0F0F0F) << 4);
+ t = ((t >> 8) & 0x00FF00FF00FF00FF) | ((t & 0x00FF00FF00FF00FF) << 8);
+ t = ((t >> 16) & 0x0000FFFF0000FFFF) | ((t & 0x0000FFFF0000FFFF) << 16);
+ t = (t >> 32) | (t << 32);
+ return t;
+ },
+ 128 => {
+ var t: T = a;
+ t = ((t >> 1) & 0x55555555555555555555555555555555) | ((t & 0x55555555555555555555555555555555) << 1);
+ t = ((t >> 2) & 0x33333333333333333333333333333333) | ((t & 0x33333333333333333333333333333333) << 2);
+ t = ((t >> 4) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F) | ((t & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F) << 4);
+ t = ((t >> 8) & 0x00FF00FF00FF00FF00FF00FF00FF00FF) | ((t & 0x00FF00FF00FF00FF00FF00FF00FF00FF) << 8);
+ t = ((t >> 16) & 0x0000FFFF0000FFFF0000FFFF0000FFFF) | ((t & 0x0000FFFF0000FFFF0000FFFF0000FFFF) << 16);
+ t = ((t >> 32) & 0x00000000FFFFFFFF00000000FFFFFFFF) | ((t & 0x00000000FFFFFFFF00000000FFFFFFFF) << 32);
+ t = (t >> 64) | (t << 64);
+ return t;
+ },
+ else => unreachable,
+ }
+}
+
+pub fn __bitreversesi2(a: u32) callconv(.C) u32 {
+ return bitreverseXi2(u32, a);
+}
+
+pub fn __bitreversedi2(a: u64) callconv(.C) u64 {
+ return bitreverseXi2(u64, a);
+}
+
+pub fn __bitreverseti2(a: u128) callconv(.C) u128 {
+ return bitreverseXi2(u128, a);
+}
+
+test {
+ _ = @import("bitreversesi2_test.zig");
+ _ = @import("bitreversedi2_test.zig");
+ _ = @import("bitreverseti2_test.zig");
+}
lib/compiler_rt/bitreversedi2_test.zig
@@ -0,0 +1,22 @@
+const bitreverse = @import("bitreverse.zig");
+const testing = @import("std").testing;
+
+fn test__bitreversedi2(input: u64, expected: u64) !void {
+ const result = bitreverse.__bitreversedi2(input);
+ try testing.expectEqual(expected, result);
+}
+
+test "bitreversedi2" {
+ try test__bitreversedi2(0x0123456789abcdef, 0xf7b3d591e6a2c480);
+ try test__bitreversedi2(0xf7b3d591e6a2c480, 0x0123456789abcdef);
+ try test__bitreversedi2(0x89abcdef00000000, 0x00000000f7b3d591);
+ try test__bitreversedi2(0x00000000f7b3d591, 0x89abcdef00000000);
+ try test__bitreversedi2(0x0000c0da23000000, 0x000000c45b030000);
+ try test__bitreversedi2(0x000000c45b030000, 0x0000c0da23000000);
+ try test__bitreversedi2(0x000000000000032f, 0xf4c0000000000000);
+ try test__bitreversedi2(0xf4c0000000000000, 0x000000000000032f);
+ try test__bitreversedi2(0xaaaaaaaaaaaaaaaa, 0x5555555555555555);
+ try test__bitreversedi2(0x5555555555555555, 0xaaaaaaaaaaaaaaaa);
+ try test__bitreversedi2(0x0000000000000000, 0x0000000000000000);
+ try test__bitreversedi2(0xffffffffffffffff, 0xffffffffffffffff);
+}
lib/compiler_rt/bitreversesi2_test.zig
@@ -0,0 +1,22 @@
+const bitreverse = @import("bitreverse.zig");
+const testing = @import("std").testing;
+
+fn test__bitreversesi2(input: u32, expected: u32) !void {
+ const result = bitreverse.__bitreversesi2(input);
+ try testing.expectEqual(expected, result);
+}
+
+test "bitreversesi2" {
+ try test__bitreversesi2(0x01234567, 0xe6a2c480);
+ try test__bitreversesi2(0xe6a2c480, 0x01234567);
+ try test__bitreversesi2(0x89abcdef, 0xf7b3d591);
+ try test__bitreversesi2(0xf7b3d591, 0x89abcdef);
+ try test__bitreversesi2(0xc0da2300, 0x00c45b03);
+ try test__bitreversesi2(0x00c45b03, 0xc0da2300);
+ try test__bitreversesi2(0x0000032f, 0xf4c00000);
+ try test__bitreversesi2(0xf4c00000, 0x0000032f);
+ try test__bitreversesi2(0xaaaaaaaa, 0x55555555);
+ try test__bitreversesi2(0x55555555, 0xaaaaaaaa);
+ try test__bitreversesi2(0x00000000, 0x00000000);
+ try test__bitreversesi2(0xffffffff, 0xffffffff);
+}
lib/compiler_rt/bitreverseti2_test.zig
@@ -0,0 +1,22 @@
+const bitreverse = @import("bitreverse.zig");
+const testing = @import("std").testing;
+
+fn test__bitreverseti2(input: u128, expected: u128) !void {
+ const result = bitreverse.__bitreverseti2(input);
+ try testing.expectEqual(expected, result);
+}
+
+test "bitreverseti2" {
+ try test__bitreverseti2(0x0123456789abcdef0123456789abcdef, 0xf7b3d591e6a2c480f7b3d591e6a2c480);
+ try test__bitreverseti2(0xf7b3d591e6a2c480f7b3d591e6a2c480, 0x0123456789abcdef0123456789abcdef);
+ try test__bitreverseti2(0x89abcdef000000000000000000000000, 0x000000000000000000000000f7b3d591);
+ try test__bitreverseti2(0x000000000000000000000000f7b3d591, 0x89abcdef000000000000000000000000);
+ try test__bitreverseti2(0x000000000000c0da2300000000000000, 0x00000000000000c45b03000000000000);
+ try test__bitreverseti2(0x00000000000000c45b03000000000000, 0x000000000000c0da2300000000000000);
+ try test__bitreverseti2(0x0000000000000000000000000000032f, 0xf4c00000000000000000000000000000);
+ try test__bitreverseti2(0xf4c00000000000000000000000000000, 0x0000000000000000000000000000032f);
+ try test__bitreverseti2(0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa, 0x55555555555555555555555555555555);
+ try test__bitreverseti2(0x55555555555555555555555555555555, 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa);
+ try test__bitreverseti2(0x00000000000000000000000000000000, 0x00000000000000000000000000000000);
+ try test__bitreverseti2(0xffffffffffffffffffffffffffffffff, 0xffffffffffffffffffffffffffffffff);
+}
lib/compiler_rt.zig
@@ -7,6 +7,7 @@ comptime {
_ = @import("compiler_rt/count0bits.zig");
_ = @import("compiler_rt/parity.zig");
_ = @import("compiler_rt/popcount.zig");
+ _ = @import("compiler_rt/bitreverse.zig");
_ = @import("compiler_rt/bswap.zig");
_ = @import("compiler_rt/cmp.zig");
src/arch/wasm/CodeGen.zig
@@ -1953,6 +1953,7 @@ fn genInst(func: *CodeGen, inst: Air.Inst.Index) InnerError!void {
.prefetch => func.airPrefetch(inst),
.popcount => func.airPopcount(inst),
.byte_swap => func.airByteSwap(inst),
+ .bit_reverse => func.airBitReverse(inst),
.slice => func.airSlice(inst),
.slice_len => func.airSliceLen(inst),
@@ -2000,7 +2001,6 @@ fn genInst(func: *CodeGen, inst: Air.Inst.Index) InnerError!void {
.mul_sat,
.assembly,
- .bit_reverse,
.is_err_ptr,
.is_non_err_ptr,
@@ -5819,6 +5819,99 @@ fn airPopcount(func: *CodeGen, inst: Air.Inst.Index) InnerError!void {
func.finishAir(inst, result, &.{ty_op.operand});
}
+fn airBitReverse(func: *CodeGen, inst: Air.Inst.Index) InnerError!void {
+ const mod = func.bin_file.base.comp.module.?;
+ const ty_op = func.air.instructions.items(.data)[@intFromEnum(inst)].ty_op;
+
+ const operand = try func.resolveInst(ty_op.operand);
+ const ty = func.typeOf(ty_op.operand);
+
+ if (ty.zigTypeTag(mod) == .Vector) {
+ return func.fail("TODO: Implement @bitReverse for vectors", .{});
+ }
+
+ const int_info = ty.intInfo(mod);
+ const bits = int_info.bits;
+ const wasm_bits = toWasmBits(bits) orelse {
+ return func.fail("TODO: Implement @bitReverse for integers with bitsize '{d}'", .{bits});
+ };
+
+ switch (wasm_bits) {
+ 32 => {
+ const intrin_ret = try func.callIntrinsic(
+ "__bitreversesi2",
+ &.{.u32_type},
+ Type.u32,
+ &.{operand},
+ );
+ const reversed = if (bits == 32)
+ intrin_ret
+ else
+ try func.binOp(intrin_ret, .{ .imm32 = 32 - bits }, Type.u32, .shr);
+ const result = try reversed.toLocal(func, ty);
+ func.finishAir(inst, result, &.{ty_op.operand});
+ },
+ 64 => {
+ const intrin_ret = try func.callIntrinsic(
+ "__bitreversedi2",
+ &.{.u64_type},
+ Type.u64,
+ &.{operand},
+ );
+ const reversed = if (bits == 64)
+ intrin_ret
+ else
+ try func.binOp(intrin_ret, .{ .imm64 = 64 - bits }, Type.u64, .shr);
+ const result = try reversed.toLocal(func, ty);
+ func.finishAir(inst, result, &.{ty_op.operand});
+ },
+ 128 => {
+ const result = try func.allocStack(ty);
+
+ try func.emitWValue(result);
+ const first_half = try func.load(operand, Type.u64, 8);
+ const intrin_ret_first = try func.callIntrinsic(
+ "__bitreversedi2",
+ &.{.u64_type},
+ Type.u64,
+ &.{first_half},
+ );
+ try func.emitWValue(intrin_ret_first);
+ if (bits < 128) {
+ try func.emitWValue(.{ .imm64 = 128 - bits });
+ try func.addTag(.i64_shr_u);
+ }
+ try func.emitWValue(result);
+ const second_half = try func.load(operand, Type.u64, 0);
+ const intrin_ret_second = try func.callIntrinsic(
+ "__bitreversedi2",
+ &.{.u64_type},
+ Type.u64,
+ &.{second_half},
+ );
+ try func.emitWValue(intrin_ret_second);
+ if (bits == 128) {
+ try func.store(.stack, .stack, Type.u64, result.offset() + 8);
+ try func.store(.stack, .stack, Type.u64, result.offset());
+ } else {
+ var tmp = try func.allocLocal(Type.u64);
+ defer tmp.free(func);
+ try func.addLabel(.local_tee, tmp.local.value);
+ try func.emitWValue(.{ .imm64 = 128 - bits });
+ try func.addTag(.i64_shr_u);
+ try func.store(.stack, .stack, Type.u64, result.offset() + 8);
+ try func.addLabel(.local_get, tmp.local.value);
+ try func.emitWValue(.{ .imm64 = bits - 64 });
+ try func.addTag(.i64_shl);
+ try func.addTag(.i64_or);
+ try func.store(.stack, .stack, Type.u64, result.offset());
+ }
+ func.finishAir(inst, result, &.{ty_op.operand});
+ },
+ else => unreachable,
+ }
+}
+
fn airErrorName(func: *CodeGen, inst: Air.Inst.Index) InnerError!void {
const un_op = func.air.instructions.items(.data)[@intFromEnum(inst)].un_op;
test/behavior/bitreverse.zig
@@ -4,13 +4,10 @@ const expect = std.testing.expect;
const minInt = std.math.minInt;
test "@bitReverse large exotic integer" {
- if (builtin.zig_backend == .stage2_wasm) return error.SkipZigTest;
-
try expect(@bitReverse(@as(u95, 0x123456789abcdef111213141)) == 0x4146424447bd9eac8f351624);
}
test "@bitReverse" {
- if (builtin.zig_backend == .stage2_wasm) return error.SkipZigTest;
if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest;
if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
if (builtin.zig_backend == .stage2_sparc64) return error.SkipZigTest; // TODO
@@ -58,6 +55,12 @@ fn testBitReverse() !void {
try expect(@bitReverse(num56) == 0x7b3d591e6a2c48);
var num64: u64 = 0x123456789abcdef1;
try expect(@bitReverse(num64) == 0x8f7b3d591e6a2c48);
+ var num95: u95 = 0x123456789abcdef111213141;
+ try expect(@bitReverse(num95) == 0x4146424447bd9eac8f351624);
+ var num96: u96 = 0x123456789abcdef111213141;
+ try expect(@bitReverse(num96) == 0x828c84888f7b3d591e6a2c48);
+ var num97: u97 = 0x1123456789abcdef111213141;
+ try expect(@bitReverse(num97) == 0x1051909111ef67ab23cd45891);
var num128: u128 = 0x123456789abcdef11121314151617181;
try expect(@bitReverse(num128) == 0x818e868a828c84888f7b3d591e6a2c48);
@@ -99,6 +102,9 @@ fn testBitReverse() !void {
&num48,
&num56,
&num64,
+ &num95,
+ &num96,
+ &num97,
&num128,
&neg8,
&neg16,