赛题点评

出题团队简介

1、设计说明

a.把浮点运算的舍入模式ROUND_NEAREST修改为ROUND_UP，使得误差积累到一定程度会产生不同的运算结果；

b.做了一个简单的宏把浮点数存储前做些移位交换，读出后再还原，这个也不算是障碍，ida下F5后会一览无余，虽然把整个表的257项都计算了，实际每个字符只用到其中一项；

c.频度自适应略作修改，每轮权重因子定长+1

2、解题思路

        0000000140002ED1                 push    rax
        0000000140002ED2                 stmxcsr dword ptr [rsp]
        0000000140002ED6                 pop     rax
        0000000140002ED7                 and     ah, 0DFh
        0000000140002EDA                 or      ah, 40h
        0000000140002EDD                 push    rax
        0000000140002EDE                 ldmxcsr dword ptr [rsp]
        0000000140002EE2                 pop     rax
        查询SSE指令集得知，这是把浮点运算的默认舍入模式ROUND_NEAREST修改为ROUND_UP

        #include <float.h>
        _set_controlfp(RC_UP,MCW_RC);

解析过程

1、分析

程序逻辑比较简单，拿 IDA 简单看看，可以看出程序的结构是将输入编码了 16 轮，与固定的输出比较。

编码过程中大量用了浮点数。将 F5 出来的验证代码直接复制出来，胡乱改一改，可以整理出还算漂亮的形式：

double XJBShuffleBit1(double x) {
  auto v = bit_cast<_QWORD>(x);
  v = ((v & 0x7FFFFFFC00ll | ((LOBYTE(v) & 7 | ((v & 0xFFFFFFFFFFFFFFF8ull) << 30)) << 6)) << 18) | ((v & 0x10000000000000ll | (((v >> 1) ^ (v ^ (v >> 1)) & 0xFFF8000000000ull) >> 14)) >> 25);
  return bit_cast<double>(v);
}
 
double XJBShuffleBit2(double x) {
  auto v = bit_cast<_QWORD>(x);
  v = ((v & 0x8000000 | ((v & 0x1FFF | (2 * (v & 0xFFFFFFFFFFFFE000ull))) << 14)) << 25) | ((v & 0x1FFFFFFF0000000ll | (((v >> 30) ^ ((unsigned int)v ^ (unsigned int)(v >> 30)) & 0x7000000) >> 6)) >> 18);
  return bit_cast<double>(v);
}
 
bool Check(unsigned char hexdecoded[32]) {
  int prob[257];              // [rsp+60h] [rbp-A0h]
  double ep[257];             // [rsp+470h] [rbp+370h]
  unsigned char bits[1024];   // [rsp+1040h] [rbp+F40h]
  unsigned char output[8192]; // [rsp+1440h] [rbp+1340h]
  unsigned char input[8192];  // [rsp+3440h] [rbp+3340h]
 
  memset(input, 0, sizeof(input));
  memset(output, 0, sizeof(output));
  memcpy(input, hexdecoded, 32);
  int input_len = 32;
  int output_len = 0;
  auto Emit = [&](int byteidx, int bitcnt = 8) {
    char packed = 0;
    for (int bi = 0; bi < bitcnt; bi++) {
      packed |= bits[8 * byteidx + bi] << (7 - bi);
    }
    output[output_len++] = packed;
  };
  for (int round = 0; round < 16; round++) {
    double lower = 0.0;
    double upper = 1.0;
 
    memset(bits, 0, sizeof(bits));
    memset(ep, 0, sizeof(ep));
    int total_bits = 0;
 
    // First 2 bytes: input_len
    *(unsigned short *)output = input_len;
    output_len = 2;
 
    for (int i = 0; i < 257; i++) {
      prob[i] = i;
    }
    unsigned int output_byte_cnt = 0;
    for (int idx = 0; idx < input_len + 5; idx++) {
      unsigned char tch = (idx < input_len) ? input[idx] : (idx & 1);
      double unit = (upper - lower) / (double)prob[256];
      for (int i = 0; i < 257; i++) {
        ep[i] = XJBShuffleBit1((double)prob[i] * unit + lower);
      }
      lower = XJBShuffleBit2(ep[tch]);
      upper = XJBShuffleBit2(ep[tch + 1]);
 
      double dlower = lower * 2.0;
      double dupper = upper * 2.0;
      while ((int)dlower == (int)dupper) {
        assert(!isnan(dlower) && !isnan(dupper));
        bits[total_bits++] = (int)dlower;
        upper = dupper - (int)dupper;
        lower = dlower - (int)dlower;
        dupper = upper * 2.0;
        dlower = lower * 2.0;
      }
      output_byte_cnt = total_bits / 8;
      total_bits %= 8;
      for (int t = 0; t < output_byte_cnt; t++) {
        Emit(t);
      }
      memmove(bits, &bits[8 * output_byte_cnt], total_bits);
      for (int j = tch + 1; j < 257; ++j) {
        prob[j] += tch % (round + 16) + round + 16;
      }
    }
    if (total_bits) {
      Emit(output_byte_cnt, total_bits);
    }
 
    memmove(input, output, output_len);
    input_len = output_len;
  }
  return output_len == 906 && memcmp(output, answer_bin, 906) == 0;
}

可以看出在浮点数运算中穿插的 XJBShuffleBit1 和 XJBShuffleBit2 互为逆运算，可以去掉。剩下的部分看起来就是一个用浮点数做的算术编码。

用浮点数做的算术编码一定存在精度问题，整理出程序之后我们首先来尝试把两边的输出对上。

随便输入一个数据（比如 0000000000000000000000000000000000000000000000000000000000000000），可以发现上面贴的代码和原始程序的输出并不相符。

打印 lower、upper、unit 并在调试器里观察对应的值，发现大约第三轮左右开始出现了最低位差 1 的情况。

遇到这种东西第一反应自然是 rounding 参数不同。

x86 CPU 有两个地方可以控制 rounding mode，一个是 FPU ControlWord，还有一个是 MXCSR。

该程序里 x87 指令和 SIMD 指令似乎都有用到（没仔细看），我们把这两个值从调试器里抄出来在自己的程序里设置上：

void InitializeCPUState() {
  fpu_control_t fpu_cw;
  _FPU_GETCW(fpu_cw);
  fprintf(stderr, "old fpu_cw = %#x\n", fpu_cw);
  fpu_cw = 0x27F;
  _FPU_SETCW(fpu_cw);
  fprintf(stderr, "new fpu_cw = %#x\n", fpu_cw);
 
  fprintf(stderr, "old MXCSR = %#x\n", _mm_getcsr());
  _mm_setcsr(0x5FA0);
  fprintf(stderr, "new MXCSR = %#x\n", _mm_getcsr());
}

设置完后会发现编码结果已经可以对上了。

2 、求解

写一个算术编码的解码程序即可。注意不要改变上述的任何计算的形式以免引入数值精度问题。考虑到数据不大，可以写的暴力一点。详细见附件。（https://bbs.pediy.com/thread-259160.htm）

运行即可得到答案504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！