« June 2017 | Main

July 25, 2017

浮点运算潜在的结果不一致问题

昨天阿楠发现了项目中的一个 bug ,是因为浮点运算的前后不一致导致的。明明是完全相同的 C 代码,参数也严格一致,但是计算出了不相同的结果。我对这个现象非常感兴趣,仔细研究了一下成因。

原始代码比较繁杂。在弄清楚原理后,我简化了出问题的代码,重现了这个问题:

static void
foo(float x) {
    float xx = x * 0.01f;
    printf("%d\n", (int)(x * 0.01f));
    printf("%d\n", (int)xx);
}

int
main() {
    foo(2000.0f);
    return 0;
}

使用 gcc 4.9.2 ,强制使用 x87 浮点运算编译运行,你会发现令人诧异的结果。

gcc a.c -mfpmath=387

19
20

前一次的输出是 19 ,后一次是 20 。

这是为什么呢?让我们来看看 gcc 生成的代码,我截取了相关的段落:

    flds    16(%rbp)
    flds    .LC0(%rip)
    fmulp   %st, %st(1)
    fstps   -4(%rbp)          ; 1. x * 0.01f 结果保存到内存中的 float 变量中
    flds    16(%rbp)
    flds    .LC0(%rip)
    fmulp   %st, %st(1)
    fisttpl -20(%rbp)        ; 2. x * 0.01f 结果直接转换为整型
    movl    -20(%rbp), %eax
    movl    %eax, %edx
    leaq    .LC1(%rip), %rcx
    call    printf
    flds    -4(%rbp)                 ; 3. 读出 1. 保存的乘法结果
    fisttpl -20(%rbp)
    movl    -20(%rbp), %eax
    movl    %eax, %edx
    leaq    .LC1(%rip), %rcx
    call    printf

这里我做了三行注释。

首先,0.01 是无法精确表示成 2 进制的,所以 * 0.01 这个操作一定会存在误差。

两次运算都是 x * 0.01f ,虽然按 C 语言的转换规则,表达式中都是 float 时,按 float 精度运算。但这里 gcc 生成的代码并没有严格设置 FPU 的精度控制,在注释 2 这个地方,乘法结果是直接从浮点寄存器转换为整数的。而在注释 1 这个地方,把乘法结果通过 fstps 以低精度形式保存到内存,再在注释 3 的地方 flds 读回。

所以在注释 2 和注释 3 的地方,浮点寄存器 st 内的值其实是有差别的,这导致了 fisttpl 转换为整数后结果不同。

July 21, 2017

防止深度包检测的一个方法

虽然以现在的加密技术,主要选择的加密算法没问题,在很长一段时间都不太用担心监听通讯的人解密获得明文。但是针对特定的加密通讯协议,还是很可能找到方法找到某种模式。这个模式不能转换为明文,但可以猜测出你是否在使用特定协议。

另外,无论你怎么加密通讯,访问特定服务流量的时间特征也可能泄露你的秘密:用什么节奏通讯,每个 ip 包多大,这些都是可供匹配的特征。

我认为,大多数情况下,通讯的稳定性是大于带宽的需求的。那么,采用本文这种方法应该能去掉上面这些流量特征。

先说说流量的时间特征。

所谓时间特征,就是通讯流量中每个字节送达的时间间隔序列。这是大多数加密算法所忽略的信息。因为通常我们不会用这个间隔序列来传递信息,也就没有必要对这个序列进行处理。但它却容易暴露协议特征。

消除这个特征的方法也很简单,我们让数据流以绝对稳定的速率传输就好了。无论有没有有效流量,我都保持绝对相同的包大小,按固定频率发送数据。只有有真正的数据需要发送时,再把数据负载到信道上,替换掉冗余流量即可。

如果保持着 64KBps 的稳定通讯带宽,7 * 24 小时工作,一个月的流量总和大约在 160GB 左右,而 linode 最便宜的 5$ 档,一个月提供的流量也有 1TB ,成本是相当低的。

如果保持一个长连接,在建立好之后就不需要监听接纳新连接进来,可以有效防止嗅探。握手协议也只发生一次,所以比较安全。

我测试了一天,从办公室宽带同美国一个机房的机器建立连接,以稳定速率发送纯随机的字符串,一整天下来都没有任何干扰。从两段的 log 分析,中间没有发生过波动。


第二是加密。

既然是有大量的闲时流量,我们也就不必浪费,完全可以利用它实现一个更好的加密。

想想量子通讯加密的原理,用量子同步一个密钥序列过去,然后用传统信道传输明文 xor 密钥 。这种方式只要保证了密钥不可能被窃听,传输的密文就是完全没有保留明文原有特征的。

我们正可利用闲时流量传输随机串,做一些简单的加密(比如使用预设的密钥),那么在真正数据载荷上,只要 xor 过去发送的随机串就可以完美加密了。在极端情况下,预先发送的随机串被消耗光,我们也至少可以获得固定带宽的一半来传输有效数据。

只要产生随机序列的算法够好:例如 linux 的随机数发生设备就会收集来自系統、驱动程序或或其它來源的环境噪音,就会比依赖有限 key 产生加密序列的算法(例如 rc4 等)要强的多。随机数列越随机,就越不可能残留模式。这样就能阻止监听者的模式分析。

通讯协议的设计也很简单,例如可以用 1bit 的标识 + 7bit 长度 + 数据块的方式来编码。只会增加 1/255 的额外负载。

在实现上,开两个线程或两个进程来做这件事情,一个线程负责以固定频率发送数据流,另一个线程负责接收有效数据流,传递给发送线程即可。


通讯信道上,我建议把上行通道和下行通道分离。至少要建立两条 TCP 连接,一条只传输数据,另一条只接收数据。

如果有条件的话,可以把两条连接走不同的 ISP ;或是同两个不同的机房建立连接,在对端两个机房间再建立通道合并在一处处理。


感谢评论中网友 dou4cc 提供补充材料:一种针对特定网站类别的网页指纹识别方法 CN 105281973 A

July 18, 2017

skynet 1.1

拖了好多天,终于决定发布 skynet 1.1 了。

距上次计划做这件事 ,除了零星的 bugfix ,还多了一些比较大的变动。

skynet 的 lua 模块全部加上了 skynet 前缀,部分数据库 driver 放到了 skynet.db 下。如果需要兼容 1.0 的路径,可以在 config 中配置 lualib/compat10 这个目录。

网络线程针对有大量写操作的应用做了很大的优化 ,在一个 实际案例 中提高了 3.5 倍的效率。

增加了一个叫做 DataSheet 的新模块,可以作为 ShareData 的一个替代选择。

由于不断发现有同学在使用 skynet 时,由于自己的 C 扩展模块实现或使用不当,导致了宕机却不清楚该如何调试。目前在 skynet 的内存分配 API 预埋了调试接口。可以通过在 make 时加上预定义宏 MEMORY_CHECK 打开。

例如,在 linux 下,可以用 make linux SKYNET_DEFINES=-DMEMORY_CHECK 打开。

btw,还有一些同学用 C 编写 lua 扩展模块没有经验,导致 lua 堆栈溢出,最终致使程序崩溃。推荐在编译 lua 的时候加上宏定义:LUA_USE_APICHECK

July 06, 2017

Paradox 的数据文件格式

Paradox 是我很喜欢的一个游戏公司,在所谓 P 社 5 萌中,十字军之王和钢铁雄心都只有浅尝,但在维多利亚和群星上均投入了大量时间和精力。

这些游戏基于同一套引擎,所以数据文件格式也是共通的。P 社开放了 Mod ,允许玩家来修改游戏,所以数据文件都是明文文本存放在文件系统中,这给了我们一个极好的学习机会:对于游戏从业者,我很有兴趣看看成熟引擎是如何管理游戏数据和游戏逻辑的。

据我所接触到的国内游戏公司,包括我们自己公司在内,游戏数据大都是基于 excel 这种二维表来表达的。我把它称为 csv 模式。这种模式的特点是,基础数据结构基于若干张二维表,每张表有不确定的行数,但每行有固定了列数。用它做基础数据结构的缺陷是很明显的,比如它很难表达树状层级结构。这往往就依赖做一个中间层,规范一些使用格式,在其上模拟出复杂数据结构。

另一种在软件行业广泛使用的基础数据结构是 json/xml 模式。json 比 xml 要简单。它的特点就是定义了两种基础的复合结构,字典和数组,允许结构嵌套。基于这种模式管理游戏数据的我也见过一些。不过对于策划来说,编辑树结构的数据终究不如 excel 拉表方便。查看起来也没有特别好的可视化工具,所以感觉用的人要少一些。

最开始,我以为 P 社的数据文件是偏向于后一种 json 模式。但实际研究下来又觉得有很大的不同。今天我尝试用 lpeg 写了一个简单的 parser 试图把它读进 lua vm ,写完 parser 后突然醒悟过来,其实它就是基于的嵌套 list ,不正是 lisp 吗?想明白这点后,有种醍醐灌顶的感觉,的确 lisp 模式要比 json 模式简洁的多,并不比 csv 模式复杂。但表达能力却强于它们两者,的确是一个更好的数据组织方案。

我们来看一个从群星中随便摘录的例子(有点长,但挺有代表性):

country_event = {
    id = primitive.16
    hide_window = yes

    trigger = {
        is_country_type = primitive
        has_country_flag = early_space_age
        #NOT = { has_country_flag = recently_advanced }
        OR = {
            AND = {
                exists = from
                from = {
                    OR = {
                        is_country_type = default
                        is_country_type = awakened_fallen_empire
                    }
                }
            }
            years_passed > 25
        }
    }

    mean_time_to_happen = {
        years = 100

        modifier = {
            factor = 0.6
            has_country_flag = acquired_tech
        }
    }

    immediate = {
        remove_country_flag = early_space_age
        set_country_flag = primitives_can_into_space
        set_country_type = default
        change_country_flag = random
        if = {
            limit = { is_species_class = MAM }
            set_graphical_culture = mammalian_01
        }
        if = {
            limit = { is_species_class = REP }
            set_graphical_culture = reptilian_01
        }
        if = {
            limit = { is_species_class = AVI }
            set_graphical_culture = avian_01
        }
        if = {
            limit = { is_species_class = ART }
            set_graphical_culture = arthropoid_01
        }
        if = {
            limit = { is_species_class = MOL }
            set_graphical_culture = molluscoid_01
        }
        if = {
            limit = { is_species_class = FUN }
            set_graphical_culture = fungoid_01
        }
        change_government = {
            authority = random
            civics = random
        }
        set_name = random
        if = {
            limit = {
                home_planet = {
                    has_observation_outpost = yes
                }
            }
            home_planet = {
                observation_outpost_owner = {
                    country_event = { id = primitive.17 }
                }
            }
        }
        add_minerals = 1000 # enough for a spaceport and then some
        add_energy = 500
        add_influence = 300
        capital_scope = {
            every_tile = {
                limit = {
                    has_blocker = yes
                    NOR = {
                        has_blocker = tb_decrepit_dwellings
                        has_blocker = tb_failing_infrastructure
                    }
                }
                remove_blocker = yes
            }
            while = {
                limit = { 
                    num_pops < 8
                    any_tile = {
                        has_grown_pop = no
                        has_growing_pop = no
                        has_blocker = no
                    }
                }
                random_tile = {
                    limit = {
                        has_grown_pop = no
                        has_growing_pop = no
                        has_blocker = no
                    }
                    create_pop = {
                        species = owner
                    }
                }
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_mineral_food_deposit
                set_building = "building_capital_2"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_mineral_deposit
                set_building = "building_mining_network_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_mineral_deposit
                set_building = "building_mining_network_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_farmland_deposit
                set_building = "building_hydroponics_farm_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_farmland_deposit
                set_building = "building_hydroponics_farm_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_energy_deposit
                set_building = "building_power_plant_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_energy_deposit
                set_building = "building_power_plant_1"
            }
            random_tile = {
                limit = {
                    has_grown_pop = yes
                    OR = {
                        has_building = "building_primitive_farm"
                        has_building = "building_primitive_factory"
                        has_building = no
                    }
                }
                clear_deposits = yes
                add_deposit = d_energy_deposit
                set_building = "building_power_plant_1"
            }
            remove_all_armies = yes
            create_army = {
                name = random
                owner = PREV
                species = owner_main_species
                type = "defense_army"
            }
            create_army = {
                name = random
                owner = PREV
                species = owner_main_species
                type = "defense_army"
            }
            create_army = {
                name = random
                owner = PREV
                species = owner_main_species
                type = "defense_army"
            }
            create_army = {
                name = random
                owner = PREV
                species = owner_main_species
                type = "defense_army"
            }
        }
        random_owned_ship = {
            limit = { is_ship_size = primitive_space_station }
            fleet = { destroy_fleet = THIS }
        }
    }
}

起初,我很疑惑在这个格式中,为啥赋值和相等都用的 = ,这不是容易引起歧义么?但是你从 lisp 的角度来看就简单了。等于号只是为了便于策划书写和阅读的一个变形。所谓 id = primitive.16 你可以理解为 ( id, primitive.16 ) 而 iscountrytype = default 一样可以理解为 ( iscountrytype , default ) 。 而

create_army = {
                name = random
                owner = PREV
                species = owner_main_species
                type = "defense_army"
            }

本质上是 ( create_army , ( ( name, random ) , (owner, PREV), (species, owner_main_species), (type, "defense_army") ) )

基础数据结构只要能表达出来,怎么理解这些 list 是更上层的工作,这就和我们在 csv 中去模拟树结构是一样的道理。只不过 years_passed > 25 这样的东西,被翻译成 ( years_passed, > , 25 ) 有三个元素。上层解析的时候,如果确定它是一个逻辑表达式,就很容易在 2 个元素的 list 中间插入一个 = 补全。

这种结构很容易描述一些控制结构,比如上面例子中的 if 。我还在其它数据中发现了 repeat while 等控制结构,这些都是上层的工作,和底层数据模型无关。但不得不说,lisp 模式比 csv 模式更容易做此类控制结构。

把这种数据结构翻译成 lua 也很容易:只需要用 lua table 的 array 来保存即可。但为了使用方便,可以加一个代理结构。如果上层业务想把一个 list 解析成字典,就在 cache 中临时生成一个 hash 表加快查询即可。我们甚至可以把它直接存在 C 内存中,只在 lua 中暴露出遍历以及高层的访问方法。所谓高层的访问方法指,可以直接读取 if repeat 等控制结构,或是把带 AND OR 这样的复合 list 直接翻译成一个条件表达式。