MD5 填充机制

// 用数组存储已出现的MD32结果（简化版，仅适合步数少的情况）
uint32_t visited[1000000];  // 存储4字节结果
size_t count = 0;

// 检测是否重复
int is_duplicate(uint32_t val) {
    for (size_t i = 0; i < count; i++) {
        if (visited[i] == val) return 1;
    }
    visited[count++] = val;
    return 0;
}

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "uthash.h"  // 需包含uthash头文件

// 哈希表节点结构：存储MD32结果和首次出现的步数
typedef struct {
    uint32_t md32_val;  // 键：MD32计算出的4字节结果
    int step;           // 记录首次出现的步数
    UT_hash_handle hh;  // UT hash内部使用的句柄
} HashNode;

HashNode *visited = NULL;  // 哈希表根指针

// 向哈希表添加值并检查是否重复
int check_and_add(uint32_t val, int step) {
    HashNode *node;
    // 查找当前值是否已存在
    HASH_FIND_INT(visited, &val, node);
    if (node) {
        // 找到重复值，返回首次出现的步数
        return node->step;
    } else {
        // 新增节点
        node = (HashNode*)malloc(sizeof(HashNode));
        node->md32_val = val;
        node->step = step;
        HASH_ADD_INT(visited, md32_val, node);  // 添加到哈希表
        return -1;  // 未重复
    }
}

// 假设的MD32哈希函数（需替换为你的实际实现）
// 输入：4字节数据，输出：4字节哈希结果
uint32_t md32_hash(uint32_t input) {
    // 此处替换为你的MD32算法实现
    // 示例：简单异或（仅作占位，实际需替换）
    return input ^ 0xDEADBEEF;
}

int main() {
    uint32_t current = 0x00000000;  // 起始值：4字节全0
    int step = 0;
    int prev_step;

    printf("开始迭代检测（起始值：0x%08X）...\n", current);

    // 先添加起始值到哈希表
    check_and_add(current, step);

    while (1) {
        step++;
        // 计算下一个MD32结果
        current = md32_hash(current);

        // 检查是否重复
        prev_step = check_and_add(current, step);
        if (prev_step != -1) {
            printf("发现循环！第%d步与第%d步结果相同：0x%08X\n", 
                   step, prev_step, current);
            break;
        }

        // 每100万步打印一次进度
        if (step % 1000000 == 0) {
            printf("已迭代%d步，当前值：0x%08X\n", step, current);
        }
    }

    // 释放哈希表内存
    HashNode *current_node, *tmp;
    HASH_ITER(hh, visited, current_node, tmp) {
        HASH_DEL(visited, current_node);
        free(current_node);
    }

    return 0;
}

// 检查是否存在恢复文件
if (file_exists("recovery.state")) {
    // 恢复模式：加载所有持久化状态
    load_processed_bitmap("processed.dat");       // 加载已处理标记到内存
    load_current_trace("current_trace.dat");       // 加载当前追踪的路径
    load_checkpoint_meta("checkpoint_meta.dat");   // 加载checkpoint元信息
    step = recovered_step;
    current_val = recovered_val;
} else {
    // 首次运行：初始化状态
    init_processed_bitmap();  // 全部标记为未处理（0）
    step = 0;
    current_val = 0x00000000;  // 初始起点
    mark_processed(current_val);  // 标记初始值为已处理
}

#define TOTAL_BITS (1ULL << 32)  // 2^32个值
#define BITMAP_SIZE (TOTAL_BITS / 8)  // 512MB

uint8_t *processed_bitmap;  // 内存中的bit数组

// 初始化：全部置0（未处理）
void init_processed_bitmap() {
    processed_bitmap = malloc(BITMAP_SIZE);
    memset(processed_bitmap, 0, BITMAP_SIZE);
}

// 标记值为已处理（bit置1）
void mark_processed(uint32_t val) {
    uint64_t idx = val / 8;       // 字节索引
    uint8_t bit = val % 8;        // 位索引
    processed_bitmap[idx] |= (1 << bit);
}

// 检查值是否已处理
int is_processed(uint32_t val) {
    uint64_t idx = val / 8;
    uint8_t bit = val % 8;
    return (processed_bitmap[idx] & (1 << bit)) != 0;
}

// 同步到磁盘（仅同步修改过的块，优化IO）
void sync_processed_bitmap(const char *path) {
    FILE *f = fopen(path, "rb+");
    if (!f) f = fopen(path, "wb");
    fwrite(processed_bitmap, 1, BITMAP_SIZE, f);
    fclose(f);
}

// 保存当前状态（用于恢复）
void save_current_trace(const char *path, uint32_t current_val, size_t step, HashNode *hash) {
    FILE *f = fopen(path, "wb");
    fwrite(&current_val, sizeof(current_val), 1, f);
    fwrite(&step, sizeof(step), 1, f);
    // 保存哈希表大小和内容（仅当前内存中的链）
    size_t hash_size = HASH_COUNT(hash);
    fwrite(&hash_size, sizeof(hash_size), 1, f);
    HashNode *node;
    for (node = hash; node; node = node->hh.next) {
        fwrite(&node->md32_val, sizeof(node->md32_val), 1, f);
        fwrite(&node->step, sizeof(node->step), 1, f);
    }
    fclose(f);
}

// 加载当前状态（恢复中断）
void load_current_trace(const char *path, uint32_t *current_val, size_t *step, HashNode **hash) {
    FILE *f = fopen(path, "rb");
    fread(current_val, sizeof(*current_val), 1, f);
    fread(step, sizeof(*step), 1, f);
    size_t hash_size;
    fread(&hash_size, sizeof(hash_size), 1, f);
    for (size_t i = 0; i < hash_size; i++) {
        uint32_t val;
        int s;
        fread(&val, sizeof(val), 1, f);
        fread(&s, sizeof(s), 1, f);
        add_to_hash(hash, val, s);  // 恢复哈希表
    }
    fclose(f);
}

int main() {
    // 1. 初始化或恢复状态
    init_or_recover_state();

    // 2. 寻找第一个未处理的起点（若恢复运行，可能需要跳过已处理值）
    uint32_t start_val = find_first_unprocessed();
    if (start_val == 0xFFFFFFFF && is_processed(start_val)) {
        printf("所有值已处理，程序结束。\n");
        return 0;
    }
    current_val = start_val;
    step = 0;
    mark_processed(current_val);
    add_to_hash(&current_hash, current_val, step);

    // 3. 主循环：追踪当前起点的路径
    while (1) {
        step++;
        current_val = md32_hash(current_val);  // 计算下一个值

        // 检查是否已处理（避免重复追踪）
        if (is_processed(current_val)) {
            // 检查是否形成循环（当前链汇入已处理的环或链）
            if (is_in_current_hash(current_hash, current_val, &prev_step)) {
                output_cycle(start_val, current_hash, prev_step, step);
            } else {
                output_chain(start_val, current_hash, current_val);  // 汇入其他已处理结构
            }
            // 寻找下一个起点
            start_val = find_first_unprocessed();
            if (start_val == 0xFFFFFFFF && is_processed(start_val)) break;
            reset_current_hash(&current_hash);  // 清空当前哈希表
            current_val = start_val;
            step = 0;
            mark_processed(current_val);
            add_to_hash(&current_hash, current_val, step);
        } else {
            // 未处理，继续追踪
            mark_processed(current_val);
            add_to_hash(&current_hash, current_val, step);
        }

        // 定期同步状态（防中断）
        if (step % 1000 == 0) {
            sync_state();
            printf("已同步状态，当前步数：%zu\n", step);
        }
    }

    // 4. 全部处理完成，汇总结果
    output_summary();
    return 0;
}