分类目录归档:开发向

xinetd-kafel – 一个更安全的xinetd服务

为了保证CTF解题/渗透赛中PWN服务有更稳定的表现(预防搅屎棍)和CTF攻防赛中有人使用ptrace/seccomp等系统调用做通用防御,我在xinetd中加入了对syscall的过滤。感谢Google的Kafel项目,给编写seccomp bpf代码提供了一种更方便的方法。

0x00 前言:为啥要搞这个东西?

众所周知,在CTF线下赛中,各大主办方明令禁止使用通用防御软件/规则对赛题进行防御。但是目前在国内外的各大比赛中,PWN题目多用socat或xinetd提供服务。而这两个组建都太过简陋,无法提供精细的系统调用控制,主办方对通防工具的检查多为人工登陆gamebox检查。
在近日结束的一场线下赛中,某战队向我反馈成功的使用了我在去年编写的一个PWN通防工具苟到了最后(关于这个工具的原理如果有兴趣欢迎star一下对应项目,人数多的话我会再开坑写文章)。
我也惊讶于主办方竟然对这么大型的通防工具都没有察觉。

而在CTF解题赛/渗透赛中,虽然有docker这一容器技术可以为pwn题目隔离运行环境,限制运行资源,方便重启等维护工作,但依然难以避免有部分搅屎选手采用诸如Fork炸弹等手段对服务器进行DoS攻击。
因此,对一些用不到的的系统调用进行限制,也可以大大减少搅屎棍选手的数量。(Docker已直接支持对container内程序进行系统调用限制Read More

因此,xinetd-kafel这一改版的xinetd服务油然而生。

0x01 原理:你对xinetd做了点啥?

其实修改xinetd让其支持对系统调用的过滤这一想法最早在Defcon 2015 Final时就已被其主办方实现。但主办方并未开源其xinetd代码(也可能是我没找到),而且其只能在xinetd的配置文件中对syscall进行简单的黑白名单过滤,难以有效限制日渐增长的搅屎大军。
让程序支持syscall过滤通常来讲有两种办法:
1. ptrace
2. seccomp
其中,ptrace就是linux下gdb用来调试程序所使用的syscall,而且其功能如其名,process trace, 用于跟踪进程的各种调用。
但是由于ptrace使用过于复杂,我们在xinetd中,并未使用这一方式,而采用了seccomp。

seccomp是个啥?

seccomp - operate on Secure Computing state of the process
seccomp 中文直译就是“操作进程的安全计算状态”,其实就是通知内核对进程的系统调用进行限制。几年前CentOS/RedHat Linux默认启用的selinux底层就是使用的这个系统调用对进程进行系统调用限制。当年应该人人装完linux的第一件事就是关掉selinux。现在的Ubuntu和CentOS都已不再默认安装或开启selinux了。
通过man seccomp我们就能看到seccomp的相关调用方法。

prctl(PR_SET_SECCOMP, SECCOMP_MODE_XX, args);
seccomp(SECCOMP_MODE_XX, flags, args);

linux Man page对seccomp的描述非常有歧义,其提供了如上两种接口,这里我把其参数相应的对应了起来。seccomp的第二个参数flags很难查到相关资料,而且在我们的场景下并不影响使用,就不再多做解释。seccomp调用会对当前进程及其子进程生效,如果我们调用seccomp之后,当前进程的系统调用就会被限制。

SECCOMP_MODE_XX共有两种选择:
1. SECCOMP_MODE_STRICT
2. SECCOMP_MODE_FILTER

SECCOMP_MODE_STRICT 会将系统调限制在 read, write, _exit (but not exit_group), sigreturn中。 我们可以编写一个小程序测试一下:

#include <stdio.h>
#include <linux/seccomp.h>
#include <linux/filter.h>
#include <linux/audit.h>
#include <linux/signal.h>
#include <sys/prctl.h>
#include <unistd.h>

int main(void)
{
    puts("a");
    prctl(PR_SET_SECCOMP, SECCOMP_MODE_STRICT, 0);
    puts("b");
    system("echo c");
    return 0;
}

编译运行后结果如下:

xm1994@xm1994-vm:~$ ./a.out 
a
b
Killed

程序在执行到system函数后就提示了Killed。这是因为在执行system时,会调用fork和execve两个系统调用。
如果我们删掉system()函数后再运行呢?程序依然会提示killed。这个问题是由于在新版的libc中,main函数退出后。libc_start_main会调用exit_group(0)结束程序以及其子进程(感觉是为了防止僵尸进程?),但再旧版的libc中,执行的是exit()。

SECCOMP_MODE_FILTER 模式则允许传入一个过滤器参数,进行自定义的系统调用过滤。

这过滤器咋搞啊?

seccomp使用的过滤器叫BPF, 允许在内核中直接设置数据包过滤模式。 我们使用wireshark/tcpdump进行网络抓包时,设置的抓包规则就会被编译成bpf送入内核。在内核中,系统调用流程也会反映在网络数据包(特殊的)的处理流程中(还有很多其他的系统事件也会以数据包的形式存在)。因此,我们也可以通过编译bpf规则到内核中,来自定义seccomp的过滤规则。

 struct sock_fprog {
    unsigned short      len;    /* Number of BPF instructions */
    struct sock_filter *filter; /* Pointer to array of
                                    BPF instructions */
};

Each program must contain one or more BPF instructions:

struct sock_filter {            /* Filter block */
    __u16 code;                 /* Actual filter code */
    __u8  jt;                   /* Jump true */
    __u8  jf;                   /* Jump false */
    __u32 k;                    /* Generic multiuse field */
};

bpf规则实际上是在内核中的bpf虚拟机中运行,也就是说他也是一种opcode,因此,我们需要一些工具去生成相应的opcode。一个比较常用的工具是libseccomp,它可以通过一些接口来生成bpf规则代码。但使用libseccomp的话就需要自己写一个parser去调用相关的接口了。万幸,在调研中,我发现了谷歌的某个员工编写的kafel库, 他可以很方便的将文本描述的过滤规则编译成sock_fprog结构体。

0x02 修改:你到底改了点啥?

在阅读了xinetd代码后,发现其代码结构是相当的干净易于理解的。我在其配置文件parser中添加了kafel_rule 这一选项,用于指定kafel规则文件。随后将文件编译为sock_fprog结构体保存在每个service的配置中。
xinetd在接收到连接后会fork出来一个子进程,随后通过dup/dup2进行流重定向。在流重定向完成后,会调用execve执行目标服务程序。这一过程类似于在shell中执行程序并对流重定向,如果读者实现过简易的shell,应该很好理解。
我们只需要在execve之前调用 prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, args); 便可对目标服务程序设定seccomp规则。

这一修改其实十分简单,代码的总变更行数不超过200行。

0x03 效果:真管用?

当然管用了,不信自己试试。

这个版本的xinetd我们已经应用到了战队布置pwn题使用的docker image:ctf-xinetd中。欢迎各位大师傅脱下来试用,好用的话别忘点个star~。

0x04 目标:理想很丰满

这个工具我用了不到六个小时就写完了。之所以这么赶时间,是希望在即将到来的国赛和以后的比赛中,能有主办方使用和推广这一工具,为选手提供更加干净公平的比赛环境。最终目的当然是国内外的所有比赛都能用上这一工具,但是理想很丰满,怕是到最后只有我们战队和比较熟悉的几个战队办比赛才会用吧233333。

Appium在Android UI测试中的应用

Android测试工具与Appium简介

Appium是一个C/S架构的,支持Android/iOS Native, Hybrid 和 Mobile Web Apps的测试框架,与测试程序通过Selenum Webdriver协议通讯。Webdriver的好处是通过HTTP RPC的方式调用Server上的过程,编写测试脚本不受语言的限制,无论是Python, Java, NodeJS均可以方便的编写测试。本文中将使用Python进行编程。

起因是因为市场部的同事抛来如下需求:批量添加一些微信好友。直接抓取请求进行重放的方法是不靠谱的,微信与服务端的通讯均加密,Pass。考虑使用xposed等框架hook相关函数进行操作。但是xposed需要越狱,且开发复杂,Pass。后来想到了使用UI测试工具进行模拟操作,开发较为简单。

Android UI测试工具有很多种,如Monkey, UIAutomator, Selendroid, Robotium等。其中UIAutomator, Monkey, Selendroid均为非侵入式的UI测试,也就是不需要修改源代码,只要安装了目标程序就可以进行测试。Robotium需要与源码一同编译测试。Appium实际上就是一个测试工具的统一调度软件,将不同的非侵入式测试工具整合在一起,对外提供统一的API。在Android 2.3以前的版本,Appium会调用Selendroid,之后的版本会直接使用UIAutomator,iOS下使用UIAutomation。Appium还支持FirefoxOS的UI测试。

Appium Gif

安装Appium

官网给出了命令行下的安装方法。但实际上Appium有GUI版本,更适合在Windows/MacOS下使用。Windows下需要安装.NET Framework。

> brew install node      # get node.js
> npm install -g appium  # get appium
> npm install wd         # get appium client
> appium &               # start appium
> node your-appium-test.js

Appium需要依赖Android SDK编译在手机端运行的两个插件,因此需要首先安装相应的Android SDK版本。这里直接使用了Android Studio中自带的SDK Manager。在SDKManager中选择和测试机相对应的SDK Platform和较新的Build-tools,如果需要使用模拟器测试还要装对应的ARM/x86 System Image,以及Intel HAXM Installer,用于加速x86虚拟机。Appium使用adb来与目标机器通讯,因此对于真机和模拟器操作几乎都是相同的,如何建立模拟器在此不再赘述。

安装完成后需要在Appium GUI中配置Android SDK目录,随后选择Android,点击Launch就可以启动Appium Server。

Appium-android-sdkAppium-launch

Appium Server默认会监听http://localhost:4723 ,用于RPC通讯。下面我们就可以打开熟悉的编程环境,编写UI测试用例了。这里使用Python进行编写,需要先安装Appium的Python Client  ,然后再python中使用appium.webclient就可以连接Appium server了。

pip install Appium-Python-Client

使用Appium进行UI控制

根据注释修改相应属性后即可运行测试。手机需要打开ADB调试,执行完以下代码后,Appium会在手机上安装Appium Settings和Unlock两个程序,随后微信会被启动。

from appium import webdriver

desired_caps = {}
desired_caps['platformName'] = 'Android'  #测试平台
desired_caps['platformVersion'] = '5.1'   #平台版本
desired_caps['deviceName'] = 'm3_note'    #设备名称,多设备时需区分
desired_caps['appPackage'] = 'com.tencent.mm'  #app package名
desired_caps['appActivity'] = '.ui.LauncherUI' #app默认Activity
dr = webdriver.Remote('http://localhost:4723/wd/hub', desired_caps) #启动Remote RPC

Selenum Webdriver使用了一种类似于JS中的DOM模型的方法来选择页面中的元素。dr为当前正在活动的activity对象,可以使用findElementByXXX的方法来获取Activity中的元素。所有Element后带s的函数,均获得所有匹配的元素,不带s的函数获得第一个匹配的元素。

查询函数

1. findElement(s)ByName

在Android中基本没用。Android UI没有Name这个属性。有说可以使用text值获取。但我并没有成功

2. findElement(s)ByClassName

通过类名来获取元素,用法如下:

item_list = dr.find_elements_by_class_name("android.widget.LinearLayout")
item_list[2].click()

3. findElementById

通过resource_id来获取元素,每个Activity中都是唯一的,用法如下

t = dr.find_element_by_id("com.tencent.mm:id/f7")
t.send_keys(wechatId)

4. findElement(s)ByAccessbiltiyId

在Android上AccessbilityID实际就是contentDescription。这个属性是为了方便视力受损人士使用手机所设置。开启TTS后系统会朗读相关控件的contentDescription。

5. findElement(s)ByXPath

通过XML Path描述来寻找元素。我没有成功的获取到,可能是XPath写的有问题。

s = dr.find_element_by_xpath("//android.widget.TextView[contains(@text,'搜索')]")
s.click()

6. findElementByAndroidUIAutomator

通过UIAutomator的选择器来获取元素。因为Appium在Android上实际是调用的UIAutomator,所以可以通过UIAutomator的选择器来选择元素。

el = dr.find_element_by_android_ui_automator("new UiSelector().text(\"搜索\")")
el.click()

操作函数

操作函数用于操作选定的元素,有很多,以下仅列举几个,更多的请查阅手册。

  1. click
  2. send_keys
  3. clear

查询函数返回的元素对象可以像JS中的dom元素一样,继续使用查询函数来选定其子元素。用例如下。

search = dr.find_element_by_id("com.tencent.mm:id/aqw").find_element_by_class_name("android.widget.RelativeLayout")
search.click()

如何确定查询规则

了解了相关的函数后,下面就应对UI进行定位了。如果是自己团队开发的程序,推荐让开发同学在所有的空间上都添加resource_id进行绝对定位。如果碰到没有谈价resource_id的元素,那就要使用别的办法进行定位了。

1. UI Automator Viewer

UI Automator Viewer是Android官方的UI定位工具,位于sdk/tools下。运行后会打开viewer界面。点击获取按钮即可获取当前正在运行的Activity的UI结构。

uiviewer

2. AppiumDriver getPageSource

AppiumDriver(Client) 可以很方便的获得当前正在运行的Activity的UI描述,随后可根据返回的XML文档来寻找元素。

print dr.page_source

getSource

(图片与他人,侵删)

确定元素位置后,即可根据前述的Find方法来查找/选择元素

编写完整的测试代码

正确的获取元素之后便可以获取元素相关的信息,随后使用各语言常用的测试框架编写测试即可,如Java的JUnit,Nodejs的Mocha等。

这里我使用Appium主要是为了模拟用户点击添加微信好友,所以完整的程序并没有使用到测试框架。相关的UI元素获取/操作方法供大家参考。

# coding:utf-8
from appium import webdriver
from time import sleep


def addFriend(dr, id, dryRun=False):
    succ = False
    wechatId = str(id)
    dr.find_element_by_accessibility_id(r"更多功能按钮").click()
    item_list = dr.find_elements_by_class_name("android.widget.LinearLayout")
    try:
        item_list[2].click()
    except:
        print "Error! in item list len"
        return succ
    el = dr.find_element_by_class_name("android.widget.ListView")
    item_list = el.find_elements_by_class_name("android.widget.LinearLayout")
    try:
        item_list[1].click()
    except:
        print "Error! in item list len"
        return succ
    t = dr.find_element_by_id("com.tencent.mm:id/f7")
    t.send_keys(wechatId)
    search = dr.find_element_by_id("com.tencent.mm:id/aqw").find_element_by_class_name("android.widget.RelativeLayout")
    search.click()
    try:
        freq = dr.find_element_by_id('com.tencent.mm:id/aqq')
        assert freq.text == u"操作过于频繁,请稍后再试。"
        print "Frequency too high! Sleep 300s"
        sleep(60)
        return succ
    except:
        pass

    try:
        dr.find_element_by_id('com.tencent.mm:id/a8x').click()
        addBtn = dr.find_element_by_id('com.tencent.mm:id/eu')
        if not dryRun:
            addBtn.click()
            succ = True
        print "Success Send Requests:" + wechatId
    except:
        print "No Such User Or Already a Friend:" + wechatId

    while True:
        try:
            dr.find_element_by_id('com.tencent.mm:id/fb').click()
        except:
            try:
                dr.find_element_by_id('com.tencent.mm:id/f4').click()
            except:
                break
    return True

def resetActivity(dr, desired_caps):
    dr.start_activity(desired_caps['appPackage'], desired_caps['appActivity'])

desired_caps = {}
desired_caps['platformName'] = 'Android'
desired_caps['platformVersion'] = '5.1'
desired_caps['deviceName'] = 'm3_note'
desired_caps['appPackage'] = 'com.tencent.mm'
desired_caps['appActivity'] = '.ui.LauncherUI'
print "Trying connect to phone..."
dr = {}
try:
    dr = webdriver.Remote('http://localhost:4723/wd/hub', desired_caps)
except Exception, e:
    print "Cannot Connect to phone :", e
    exit()
print "Successfully connect to phone."
print "Reading friend list..."
friendList = []
fp = open("friends.txt")
line = fp.readline().strip()
while line:
    friendList.append(line)
    line = fp.readline().strip()
print "Finish reading friends. Total: " + str(len(friendList))
print "Wait for Wechat's splash screen...."
for i in range(0, 10):
    print 10 - i
    sleep(1)
succ_list = []
fail_list = []
for i in friendList:
    try:
        succ = addFriend(dr, i, dryRun=False)
        if succ:
            succ_list.append(i)
        else:
            fail_list.append(i)
    except:
        fail_list.append(i)
        resetActivity(dr, desired_caps)

print "Succeed List:"
print "\n".join(succ_list)
print "Failed List:"
print "\n".join(fail_list)

dr.close()

 

HttpLuaModule在Coding WebIDE中的应用

0x00 前言

HttpLuaModule又名ngx_lua,由国人大神agentzh(章奕春)开发。ngx_lua将lua脚本语言嵌入nginx中,并用lua封装了部分nginx的API,使nginx开发不再需要繁琐的C语言进行。目前,ngx_lua在阿里cdn,又拍云cdn中均发挥了极大的作用。

Coding作为一个技术导向的创业公司,也在Coding WebIDE混合架构中使用了ngx_lua。

0x01 ngx_lua介绍

ngx_lua 通过在nginx的处理阶段中使用lua或luajit(推荐)插入lua脚本,对当前阶段的请求进行处理,使nginx具有更复杂的逻辑功能。由于lua的紧凑、快速以及内建协程,所以在保证高并发服务能力的同时极大地降低了业务逻辑实现成本。

推荐阅读浅谈 ngx_lua 在 UPYUN 的应用

0x02 应用背景

Coding WebIDE是国内第一个基于Web的集成开发环境(IDE),目前提供给用户一定的代码储存空间和一个完整的Ubuntu Terminal用于在线调试

由于IDE在使用的过程中存在状态,因此每个用户的每个Workspace必须存放在某台固定的机器上。这就要求Balancer将用户每次分配到相同的机器上。

在引入ngx_lua前,Service会在用户创建Workspace时将用户所在的机器名返回给Web UI,Web UI在每次Ajax请求的时候会带上`X-Space-Key` 和 `X-Sharding-Group`两个HTTP Header,nginx在请求中根据X-Sharding-Group的值来选择对应的Service。这里将后端的机器名暴露给了用户,带来了安全隐患。

Coding WebIDE还有一个生成访问URL的功能,可将用户在Terminal中启动的Http Application暴露在公网中,供用户调试使用。

在引入ngx_lua前,每次对访问URL的请求都会进入Service,由Service找到对应Container的IP,并通过`X-Accel-Redirect`的方式通知每个Service中的nginx,去返回目标Container中的服务。而在这个过程中,用户的请求会两次经过Service层的nginx,造成较大的延时。

0x03 ngx_lua的应用

Balancing

我们使用ngx_lua将原本需要在X-Sharding-Group头中的backend地址去掉,通过ngx_lua在数据库和缓存中检索X-Space-Key来找到对应的Service,并将upstream设为对应机器,杜绝了请求中带有Service机器名带来的隐患。同时,Redis作为缓存的加入并不会导致性能有太大的降低。

if ngx.var.backend_upstream ~= "" then
	ngx.log(ngx.ALERT, ngx.var.backend_upstream, " From Header")
	return
end

local spaceKey = ngx.req.get_headers()['X-Space-Key']
targetGroup = config.defaultGroup
redisCli = init_redis()
mysqlConn = init_mysql()
if spaceKey ~= nil then
	local shardingGroup, err = 在缓存中查询
	if shardingGroup ~= nil and shardingGroup ~= ngx.null then
		targetGroup = shardingGroup
		ngx.log(ngx.ALERT, shardingGroup, " From Redis")
	else
		res, err, errno, sqlstate = 在数据库中查询
		if not res then
			ngx.log(ngx.ERR, err)
			ngx.exit(500)
		else
			shardingGroup = res;
			if shardingGroup ~= nil then
				缓存数据
				targetGroup = shardingGroup
			end
		end
	end
end

ngx.var.backend_upstream = targetGroup
ngx.log(ngx.ALERT, "Workspace ", spaceKey, " final upstream: ",targetGroup)

close_cosock(mysqlConn)
close_cosock(redisCli)

 

 

Access URL

Access URL在引入ngx_lua后,性能得到了极大的提升。在用户生成了Access URL后,Service会将相关数据缓存入redis,在用户访问URL时,将由Frontend Balancer直接寻找对应container的信息,并直接要求Backend Service返回对应的请求。

redisCli = init_redis()

local upstream = ""

local host = ngx.req.get_headers()['host']
local spaceKey, port, token = string.match(host, "^([^-]+)-([^-]+)-([^.]+)[.]") --匹配spaceKey, port, token sdciqw-58647-eidsae.box.io ->  sdciqw, 58647, eidsae

local redisKey = spaceKey..":"..port
local jsonStr, err = redisCli:get(redisKey)
if jsonStr == nil or jsonStr == ngx.null then
	ngx.log(ngx.ERR, "access a non-exist http forwarding upstream")
else
    local luahf = cjson.decode(jsonStr)
    if luahf.token == token and luahf.ip ~= cjson.null  then
        upstream = luahf.host.."/"..luahf.ip.."/"..port..ngx.var.request_uri
    end
end
close_cosock(redisCli)
ngx.log(ngx.ALERT, "Http forwarding upstream: ", upstream)
if upstream == "" then
	ngx.exit(502)
else
	ngx.var.upstream = upstream
end

原本需要nginx转发两次的请求现在只需要一次就可以到达。大大提升了用户的体验。

WebSocket

由于WebSocket不能自定义Header,所以使用了类似于Access URL的方法进行Balancing。Web UI在建立WebSocket时所需的握手时间也有一定的降低。

0x04 ngx_lua的踩坑经历

cosocket在不同阶段的可用性

resty.mysql和resty.redis均采用了nginx中提供的cosocket进行socket链接。但cosocket并不是在每个nginx的访问阶段都可用。在我们第一版测试的时候使用了set_by_lua直接对nginx变量进行赋值。但是在这个阶段只能使用redis_lua和luasql.mysql进行访问。但这两个模块使用了lua原生的socket库,并不能复用nginx的socket链接。而且由于ngx_lua的特殊性,无法在外部模块中使用连接池,导致链接开销过大,速度降低等问题。

因此,我们将原在set_by_lua中执行的任务使用access_by_lua的方式重写,使用了复用cosocket的openresty系列库。

sql和redis的连接池

由于ngx_lua的特殊性,无法使用传统意义上的连接池。但是openresty提供了基于cosocket的连接池,可以减少每次重连造成的开销。

function close_cosock(cosock)
	if not cosock then
		return
	end
	local ok, err = cosock:set_keepalive(config.pool.idle_time, config.pool.size)
	if not ok then
		ngx.say("set keepalive error : ", err)
	end
end

使用如上代码关闭`resty.redis`和`resty.mysql`的链接便可将cosocket链接放入连接池,等待下次connect。

生产和开发环境不一致

根据官方文档,生产环境需要打开lua_code_cache。但是开发环境可以不打开lua_code_cache。当不打开code cache时,每次请求都会重新加载lua文件,这使得lua文件可以获得及时的更新。

在我们的测试中,当生产环境打开code cache后,部分

0x05 总结

综上,集成lua的nginx可以完成很多之前需要在Backend Service中完成的功能,可以减少不同模块之间的耦合度,还能一定程度上提升应用性能。

lua的开发周期和成本也比用C开发nginx模块要低得多,便于快速上线和迭代开发。因此,不妨尝试将部分业务放入ngx_lua中完成。

交换两数位运算快还是赋值快?

从初高中的OI到大学中的ACM,队友中都流传着交换变量用位运算要比用赋值速度快。不少人对此深信不疑。但这真的是真的么?今天就来从理论上分析这个问题的真假。

先附上今天所要测试的程序段:

编译环境:

➜  test  clang --version
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

先是赋值交换

void swap(int *a, int *b)
{
	int t=*a;
	*a=*b;
	*b=t;
}

然后是位运算交换

void swap(int *a,int *b)
{
        if(*a == *b )
                 return ;
	*a = *a ^ *b;
        *b = *b ^ *a;
        *a = *a ^ *b;
}

由于这里只是程序片段,就不再生成可执行文件。使用clang编译获得汇编文件来进行对比。

首先,我们不开编译优化,看看编译后的结果。(clang %s.c -S -o %s-no.s -m32)

赋值交换:

	.section	__TEXT,__text,regular,pure_instructions
	.globl	_swap
	.align	4, 0x90
_swap:                                  ## @swap
## BB#0:
	pushl	%ebp
	movl	%esp, %ebp              ##准备阶段
	subl	$12, %esp               ##开栈帧
	movl	12(%ebp), %eax          ## b -> %eax
	movl	8(%ebp), %ecx           ## a -> %ecx
	movl	%ecx, -4(%ebp)          ## 开本地变量
	movl	%eax, -8(%ebp)
	movl	-4(%ebp), %eax      
	movl	(%eax), %eax            ##交换两元素
	movl	%eax, -12(%ebp)
	movl	-8(%ebp), %eax      
	movl	(%eax), %eax
	movl	-4(%ebp), %ecx          ##赋回原变量
	movl	%eax, (%ecx)
	movl	-12(%ebp), %eax
	movl	-8(%ebp), %ecx
	movl	%eax, (%ecx)
	addl	$12, %esp
	popl	%ebp
	retl


.subsections_via_symbols

位运算交换:

.section	__TEXT,__text,regular,pure_instructions
	.globl	_swap
	.align	4, 0x90
_swap:                                  ## @swap
## BB#0:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	movl	12(%ebp), %eax
	movl	8(%ebp), %ecx
	movl	%ecx, -4(%ebp)
	movl	%eax, -8(%ebp)
	movl	-4(%ebp), %eax
	movl	(%eax), %eax
	movl	-8(%ebp), %ecx         ## 准备阶段都一样
	cmpl	(%ecx), %eax           ## 进行一个相等判断,下文有介绍
	jne	LBB0_2
## BB#1:
	jmp	LBB0_3
LBB0_2:
	movl	-4(%ebp), %ex
	movl	(%eax), %eax
	movl	-8(%ebp), %ecx
	xorl	(%ecx), %eax
	movl	-4(%ebp), %ecx
	movl	%eax, (%ecx)
	movl	-8(%ebp), %eax
	movl	(%eax), %eax
	movl	-4(%ebp), %ecx
	xorl	(%ecx), %eax
	movl	-8(%ebp), %ecx
	movl	%eax, (%ecx)
	movl	-4(%ebp), %eax
	movl	(%eax), %eax
	movl	-8(%ebp), %ecx
	xorl	(%ecx), %eax
	movl	-4(%ebp), %ecx
	movl	%eax, (%ecx)          ## XOR
LBB0_3:
	addl	$8, %esp
	popl	%ebp                
	retl                          ## 返回阶段


.subsections_via_symbols

很明显,赋值交换的指令数量已经比位运算交换少了不少。(待补充汇编代码分析)下面我们再打开第一级编译优化(clang %s.c -S -o %s-o1.s -O -m32)来试一下:

赋值交换:

	.section	__TEXT,__text,regular,pure_instructions
	.globl	_swap
	.align	4, 0x90
_swap:                                  ## @swap
## BB#0:
	pushl	%ebp			##%ebp 入栈
	movl	%esp, %ebp		##准备%esp
	pushl	%esi			##暂存%esi
	movl	12(%ebp), %eax		## a -> %eax
	movl	8(%ebp), %ecx		## b -> %ecx
	movl	(%ecx), %edx		## (%ecx) 此时为*b的值 -> %edx
	movl	(%eax), %esi		## (%eax) 此时为*a的值 -> %esi
	movl	%esi, (%ecx)		## %esi -> *b
	movl	%edx, (%eax)		## %edx -> *a
	popl	%esi			## 恢复 %esi
	popl	%ebp			## 弹出反址
	retl				## 返回


.subsections_via_symbols

 

位运算交换:

	.globl	_swap
	.align	4, 0x90
_swap:                                  ## @swap
## BB#0:
	pushl	%ebp                    ## %ebp入栈
	movl	%esp, %ebp              ## 准备 %esp
	pushl	%esi                    ## 暂存 %esi
	movl	12(%ebp), %ecx          ## b -> %ecx
	movl	8(%ebp), %eax           ## a -> %eax
	movl	(%eax), %esi            ## *a -> %esi 
	movl	(%ecx), %edx            ## *b -> %edx
	cmpl	%edx, %esi              ## 比较 *a *b
	je	LBB0_2                  ## 相等时跳转结束。
## BB#1:
	xorl	%esi, %edx              ## %esi(*a的值) xor %edx(*b的值) ->%edx
	movl	%edx, (%eax)            ## %edx -> %eax(*a)
	xorl	(%ecx), %edx            ##以下类似
	movl	%edx, (%ecx)
	xorl	%edx, (%eax)
LBB0_2:
	popl	%esi
	popl	%ebp
	retl


.subsections_via_symbols

赋值发在完成两个方法相同的寄存器变量准备步骤后,赋值法仅用了两个mov指令就完成了变量交换。而位运算法执行了三个xor两个mov指令才完成交换。

因此,位运算交换两数并不比赋值法快,特别在编译优化优秀的编译器上,中间变量完全可以使用寄存器优化掉。因此,放弃用位运算作交换的念头吧。

矩阵迷宫生成算法

脑残的数据结构课设要做个什么脑残的非递归迷宫问题求解。最脑残的是还让自己去生成一个迷宫。于是有了这篇文章。

言归正传。先介绍一个神奇的数据结构叫“并茶几” 哦不,“并查集”。并查集是一中用于判断元素是否属于同一集合的数据结构,主要的操作有查找和合并。并查集实际上是一个森林,每一个集合是一棵树。

在并查集中,默认每个元素的父元素指向自己,在执行合并操作的时候只需要将自己的父元素指向要合并的节点,即可完成合并。在执行查找的时候,只需要一直寻找父元素,直到父元素指向父元素本身。

但是当合并次数增多以后,可能会出现树的深度过大,导致每次回溯父节点耗时过长。这里有一种路径压缩的办法。在执行find的时候,将每个节点的父节点都改为最远处的父节点。在递归执行查找的时候只需要很小的改动即可。

还有一种按秩合并的算法可以优化并查集。但是远没有路径压缩简单易懂,在小规模数据时无需使用。

下面提供了一个简单封装过的并查集类。

#ifndef _UNIONSET_H_
#define _UNIONSET_H_
#include <vector>
class UnionSet
{
private:
	std::vector<int> Fa;
public:
	UnionSet(){}
	void Init(int n)
	{
		for (int i = Fa.size(); i <= n; ++i)
			Fa.push_back(i);
	}
	int Find(int u)
	{
		if (Fa.size() <= u)
			Init(u);
		while (u != Fa[u])
			return Fa[u] = Find(Fa[u]);
		return u;
	}
	bool Same(int x, int y)
	{
		return (Find(x) == Find(y));
	}
	int Merge(int x, int y)
	{
		x = Find(x);
		y = Find(y);
		Fa[y] = x;
		return x;
	}
	int MakeEmpty()
	{
		for (int i = 0; i < Fa.size(); ++i)
			Fa[i] = i;
	}
};

#endif

说完了并查集就该让我们谈谈怎么去生成迷宫了。

迷宫实质上就是从原点到重点的一科生成树,生成树中的所有节点必属于同一个集合。于是借助并查集和随机数构造迷宫。

在生成迷宫时,我们随机选择一堵墙,并把墙打通,隔开的两个格子在并查集中合并。直到原点和终点在同一个集合中。

vector<vector<int>> *map = nullptr;
vector<vector<bool>> *visit = nullptr;
const int LocX[4] = { 0, 1, 0, -1 };
const int LocY[4] = { 1, 0, -1, 0 };
enum Direction	{ UP, RIGHT, DOWN, LEFT };
struct Point
{
	int x, y;
};
void RamdomMap(int x, int y)
{
	system("cls");
	if (map != nullptr)
		delete map;
	map = new vector<vector<int>>(y*2 + 2, vector<int>(x*2 + 2, '0'));
	vector<vector<int>> &map = *::map;
	UnionSet us;
	int maxm = x*y;
	while (us.Find(1)!=us.Find(maxm))
	{
		int rx = (rand() % x)+1;
		int ry = (rand() % y)+1;
		rx = rx * 2 - 1;
		ry = ry * 2 - 1;
		int loc = rand() % 4;
		if ((ry + LocY[loc]<1 || ry + LocY[loc] > y*2-1) || (rx + LocX[loc]<1 || rx + LocX[loc] > x*2-1))
			continue;
		rx += LocX[loc];
		ry += LocY[loc];
		if (ry % 2 == 0)
		{
			int tx1 = rx / 2 + 1, tx2 = tx1;
			int ty1 = ry / 2, ty2 = ry / 2 + 1;
			if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
				continue;
			map[ry][rx] = '1';
			map[ry - 1][rx] = '1';
			map[ry + 1][rx] = '1';

			us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
		}
		else
		{
			int ty1 = (ry + 1) / 2, ty2 = ty1;
			int tx1 = rx / 2, tx2 = rx / 2 + 1;
			if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
				continue;
			map[ry][rx] = '1';
			map[ry][rx - 1] = '1';
			map[ry][rx + 1] = '1';

			us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
		}
		COORD pos = { 0, 0 };
		SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
		for (int j = 1; j < y*2 ; ++j)
		{
			for (int i = 1; i < x*2; ++i)
			{
				printf("%c", map[j][i]);
			}
			printf("n");
		}
		//printf("正在点(%d,%d)ttn", rx, ry);

	}
	
	FILE *fp = fopen("maze.map", "w");
	fprintf(fp,"%d %dn", x * 2 - 1, y * 2 - 1);
	for (int j = 1; j < y*2; ++j)
	{
		for (int i = 1; i < x*2; ++i)
		{
			fprintf(fp,"%c ", map[j][i]);
		}
		fprintf(fp, "n");
	}
	fclose(fp);
	delete ::map;
	::map = nullptr;
}

迷宫

以上就是用这种方法生成的迷宫矩阵。原点为(0,0),终点为(15,15)。迷宫通路较为曲折,下面是用深搜获得的解。

迷宫,解

 

这个生成算法有个缺点,因为相邻的两个点之间必有墙,所以只能生成奇数乘奇数的矩阵。如果有能生成偶数矩阵的算法,欢迎在下面留言讨论。