const std = @import("std");

const SourceMap = struct {
    const base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    const vlq_lookup_table: [256]VLQ = brk: {
        var entries: [256]VLQ = undefined;
        var i: usize = 0;
        var j: i32 = 0;
        while (i < 256) : (i += 1) {
            entries[i] = encodeVLQ(j);
            j += 1;
        }
        break :brk entries;
    };

    const vlq_max_in_bytes = 8;
    pub const VLQ = struct {
        // We only need to worry about i32
        // That means the maximum VLQ-encoded value is 8 bytes
        // because there are only 4 bits of number inside each VLQ value
        // and it expects i32
        // therefore, it can never be more than 32 bits long
        // I believe the actual number is 7 bytes long, however we can add an extra byte to be more cautious
        bytes: [vlq_max_in_bytes]u8,
        len: u4 = 0,
    };

    pub fn encodeVLQWithLookupTable(
        value: i32,
    ) VLQ {
        return if (value >= 0 and value <= 255)
            vlq_lookup_table[@intCast(usize, value)]
        else
            encodeVLQ(value);
    }

    // A single base 64 digit can contain 6 bits of data. For the base 64 variable
    // length quantities we use in the source map spec, the first bit is the sign,
    // the next four bits are the actual value, and the 6th bit is the continuation
    // bit. The continuation bit tells us whether there are more digits in this
    // value following this digit.
    //
    //   Continuation
    //   |    Sign
    //   |    |
    //   V    V
    //   101011
    //
    pub fn encodeVLQ(
        value: i32,
    ) VLQ {
        var len: u4 = 0;
        var bytes: [vlq_max_in_bytes]u8 = undefined;

        var vlq: u32 = if (value >= 0)
            @bitCast(u32, value << 1)
        else
            @bitCast(u32, (-value << 1) | 1);

        // source mappings are limited to i32
        comptime var i: usize = 0;
        inline while (i < vlq_max_in_bytes) : (i += 1) {
            var digit = vlq & 31;
            vlq >>= 5;

            // If there are still more digits in this value, we must make sure the
            // continuation bit is marked
            if (vlq != 0) {
                digit |= 32;
            }

            bytes[len] = base64[digit];
            len += 1;

            if (vlq == 0) {
                return VLQ{
                    .bytes = bytes,
                    .len = len,
                };
            }
        }

        return .{ .bytes = bytes, .len = 0 };
    }

    pub const VLQResult = struct {
        value: i32 = 0,
        start: usize = 0,
    };

    // base64 stores values up to 7 bits
    const base64_lut: [std.math.maxInt(u7)]u7 = brk: {
        @setEvalBranchQuota(9999);
        var bytes = [_]u7{std.math.maxInt(u7)} ** std.math.maxInt(u7);

        for (base64) |c, i| {
            bytes[c] = i;
        }

        break :brk bytes;
    };

    pub fn decodeVLQ(encoded: []const u8, start: usize) VLQResult {
        var shift: u8 = 0;
        var vlq: u32 = 0;

        // hint to the compiler what the maximum value is
        const encoded_ = encoded[start..][0..@minimum(encoded.len - start, comptime (vlq_max_in_bytes + 1))];

        // inlining helps for the 1 or 2 byte case, hurts a little for larger
        comptime var i: usize = 0;
        inline while (i < vlq_max_in_bytes + 1) : (i += 1) {
            const index = @as(u32, base64_lut[@truncate(u7, encoded_[i])]);

            // decode a byte
            vlq |= (index & 31) << @truncate(u5, shift);
            shift += 5;

            // Stop if there's no continuation bit
            if ((index & 32) == 0) {
                return VLQResult{
                    .start = i + start,
                    .value = if ((vlq & 1) == 0)
                        @intCast(i32, vlq >> 1)
                    else
                        -@intCast(i32, (vlq >> 1)),
                };
            }
        }

        return VLQResult{ .start = start + encoded_.len, .value = 0 };
    }
};

pub fn main() anyerror!void {
    const args = try std.process.argsAlloc(std.heap.c_allocator);
    const how_many = try std.fmt.parseInt(u64, args[args.len - 1], 10);

    var numbers = try std.heap.c_allocator.alloc(i32, how_many);
    var results = try std.heap.c_allocator.alloc(SourceMap.VLQ, how_many);
    var leb_buf = try std.heap.c_allocator.alloc(u8, how_many * 8);
    const byte_size = std.mem.sliceAsBytes(numbers).len;

    var rand = std.rand.DefaultPrng.init(0);

    std.debug.print("Random values:\n\n", .{});

    for (numbers) |_, i| {
        numbers[i] = rand.random().int(i32);
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQ(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]                encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQWithLookupTable(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (results) |n, i| {
            numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value;
        }

        const elapsed = timer.read();
        std.debug.print("[{d}]                decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var writer = stream.writer();
        for (numbers) |n| {
            std.leb.writeILEB128(writer, n) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var reader = stream.reader();
        for (numbers) |_, i| {
            numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    std.debug.print("\nNumbers between 0 - 8096:\n\n", .{});

    for (numbers) |_, i| {
        numbers[i] = rand.random().intRangeAtMost(i32, 0, 8096);
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQ(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]                encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQWithLookupTable(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (results) |n, i| {
            numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value;
        }

        const elapsed = timer.read();
        std.debug.print("[{d}]                decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var writer = stream.writer();
        for (numbers) |n| {
            std.leb.writeILEB128(writer, n) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var reader = stream.reader();
        for (numbers) |_, i| {
            numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    std.debug.print("\nNumbers between 0 - 255:\n\n", .{});

    for (numbers) |_, i| {
        numbers[i] = rand.random().intRangeAtMost(i32, 0, 255);
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQ(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]                encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (numbers) |n, i| {
            results[i] = SourceMap.encodeVLQWithLookupTable(n);
        }
        const elapsed = timer.read();
        std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();

        for (results) |n, i| {
            numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value;
        }

        const elapsed = timer.read();
        std.debug.print("[{d}]                decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var writer = stream.writer();
        for (numbers) |n| {
            std.leb.writeILEB128(writer, n) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }

    {
        var timer = try std.time.Timer.start();
        var stream = std.io.fixedBufferStream(leb_buf);
        var reader = stream.reader();
        for (numbers) |_, i| {
            numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable;
        }
        const elapsed = timer.read();
        std.debug.print("[{d}]        ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) });
    }
}

test "encodeVLQ" {
    const fixtures = .{
        .{ 2_147_483_647, "+/////D" },
        .{ -2_147_483_647, "//////D" },
        .{ 0, "A" },
        .{ 1, "C" },
        .{ -1, "D" },
        .{ 123, "2H" },
        .{ 123456789, "qxmvrH" },
    };
    inline for (fixtures) |fixture| {
        const result = SourceMap.encodeVLQ(fixture[0]);
        try std.testing.expectEqualStrings(fixture[1], result.bytes[0..result.len]);
    }
}

test "decodeVLQ" {
    const fixtures = .{
        .{ 2_147_483_647, "+/////D" },
        .{ -2_147_483_647, "//////D" },
        .{ 0, "A" },
        .{ 1, "C" },
        .{ -1, "D" },
        .{ 123, "2H" },
        .{ 123456789, "qxmvrH" },
    };
    inline for (fixtures) |fixture| {
        const result = SourceMap.decodeVLQ(fixture[1], 0);
        try std.testing.expectEqual(
            result.value,
            fixture[0],
        );
    }
}
<option value='plugin/resolvedir'>plugin/resolvedir</option>
<option value='postinstall_3'>postinstall_3</option>
<option value='repl'>repl</option>
<option value='request-body-stream'>request-body-stream</option>
<option value='reserve-commands'>reserve-commands</option>
<option value='revert-5167-dylan/decode-regex-if-needed'>revert-5167-dylan/decode-regex-if-needed</option>
<option value='rfc/bun-bundler-api'>rfc/bun-bundler-api</option>
<option value='rfc/bunfig-overhaul'>rfc/bunfig-overhaul</option>
<option value='save-in-update'>save-in-update</option>
<option value='sdl'>sdl</option>
<option value='test/action'>test/action</option>
<option value='types/mock'>types/mock</option>
<option value='types/readable-stream-default'>types/readable-stream-default</option>
<option value='types/tty'>types/tty</option>
<option value='u/vjpr/zig-0.10'>u/vjpr/zig-0.10</option>
<option value='xHyroM/types/expose-Bun-Env'>xHyroM/types/expose-Bun-Env</option>
</select> <input type='submit' value='switch'/></form></td></tr>
<tr><td class='sub'>Unnamed repository; edit this file 'description' to name the repository.</td><td class='sub right'></td></tr></table>
<table class='tabs'><tr><td>
<a href='/ansg191/bun/about/?h=dylan/non-enumerable-export-values'>about</a><a href='/ansg191/bun/?h=dylan/non-enumerable-export-values'>summary</a><a href='/ansg191/bun/refs/?h=dylan/non-enumerable-export-values'>refs</a><a class='active' href='/ansg191/bun/log/src/js/node/assert.js?h=dylan/non-enumerable-export-values&amp;follow=1'>log</a><a href='/ansg191/bun/tree/src/js/node/assert.js?h=dylan/non-enumerable-export-values'>tree</a><a href='/ansg191/bun/commit/src/js/node/assert.js?h=dylan/non-enumerable-export-values&amp;follow=1'>commit</a><a href='/ansg191/bun/diff/src/js/node/assert.js?h=dylan/non-enumerable-export-values&amp;follow=1'>diff</a></td><td class='form'><form class='right' method='get' action='/ansg191/bun/log/src/js/node/assert.js'>
<input type='hidden' name='h' value='dylan/non-enumerable-export-values'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/ansg191/bun/log/?h=dylan/non-enumerable-export-values&amp;follow=1'>root</a>/<a href='/ansg191/bun/log/src?h=dylan/non-enumerable-export-values&amp;follow=1'>src</a>/<a href='/ansg191/bun/log/src/js?h=dylan/non-enumerable-export-values&amp;follow=1'>js</a>/<a href='/ansg191/bun/log/src/js/node?h=dylan/non-enumerable-export-values&amp;follow=1'>node</a>/<a href='/ansg191/bun/log/src/js/node/assert.js?h=dylan/non-enumerable-export-values&amp;follow=1'>assert.js</a> (<a href='/ansg191/bun/log/src/js/node/assert.js?h=dylan/non-enumerable-export-values'>unfollow</a>)</div><div class='content'><table class='list nowrap'><tr class='nohover'><th class='left'>Age</th><th class='left'>Commit message (<a href='/ansg191/bun/log/src/js/node/assert.js?h=dylan/non-enumerable-export-values&amp;showmsg=1&amp;follow=1'>Expand</a>)</th><th class='left'>Author</th><th class='left'>Files</th><th class='left'>Lines</th></tr>
<tr><td><span title='2023-08-31 22:24:34 -0700'>2023-08-31</span></td><td><a href='/ansg191/bun/commit/src/js_parser.zig?h=dylan/non-enumerable-export-values&amp;id=7dd06e2a12c1696bfbce715b6baaced3fa802944&amp;follow=1'>insert `enumerable: true` when needed</a></td><td><img src='//www.gravatar.com/avatar/0f2ac0141773b63a6cd646063e7ebfca?s=13&amp;d=retro' width='13' height='13' alt='Gravatar' /> Dylan Conway
</td><td>2</td><td><span class='deletions'>-11</span>/<span class='insertions'>+120</span></td></tr>
<tr><td><span title='2023-08-31 17:36:03 -0700'>2023-08-31</span></td><td><a href='/ansg191/bun/commit/test/cli/install/bun-install.test.ts?h=dylan/non-enumerable-export-values&amp;id=59edbe645ca568aa6438f8fa53c1a567cf1159c0&amp;follow=1'>`bun install` correctly join dependency URLs (#4421)</a></td><td><img src='//www.gravatar.com/avatar/32549d62eb1f7cd349813752661f0a71?s=13&amp;d=retro' width='13' height='13' alt='Gravatar' /> Julian
</td><td>6</td><td><span class='deletions'>-64</span>/<span class='insertions'>+243</span></td></tr>
<tr><td><span title='2023-08-31 17:33:08 -0700'>2023-08-31</span></td><td><a href='/ansg191/bun/commit/test/js/web/html/FormData.test.ts?h=dylan/non-enumerable-export-values&amp;id=fef70f2473daefe242c80b9f3f34ef67396efaef&amp;follow=1'>get name if not provided in `FormData.append` (#4434)</a></td><td><img src='//www.gravatar.com/avatar/9c0e69537b9d9493708725dd4c91e3af?s=13&amp;d=retro' width='13' height='13' alt='Gravatar' /> Dylan Conway
</td><td>4</td><td><span class='deletions'>-5</span>/<span class='insertions'>+45</span></td></tr>
<tr><td><span title='2023-08-31 16:20:26 -0700'>2023-08-31</span></td><td><a href='/ansg191/bun/commit/test/bundler/bundler_cjs2esm.test.ts?h=dylan/non-enumerable-export-values&amp;id=4d944773f0234262e2df0dfd10cb564d3cdf6125&amp;follow=1'>export non-enumerable values</a></td><td><img src='//www.gravatar.com/avatar/0f2ac0141773b63a6cd646063e7ebfca?s=13&amp;d=retro' width='13' height='13' alt='Gravatar' /> Dylan Conway
</td><td>2</td><td><span class='deletions'>-4</span>/<span class='insertions'>+79</span></td></tr>
<tr><td><span title='2023-08-31 00:18:59 -0700'>2023-08-31</span></td><td><a href='/ansg191/bun/commit/packages/bun-vscode/src/features/debug.ts?h=dylan/non-enumerable-export-values&amp;id=bd7262f037589a69be8b5fb2f705666309c32b86&amp;follow=1'>Fix vscode debug terminal</a></td><td><img src='//www.gravatar.com/avatar/882f2dfc408f3f96e6e745e36d5d1d80?s=13&amp;d=retro' width='13' height='13' alt='Gravatar' /> Ashcon Partovi
</td><td>1</td><td><span class='deletions'>-21</span>/<span class='insertions'>+0</span></td></tr>