为什么要引入齐次坐标

前面我们提到了图像的缩放变换和旋转变换,可以用矩阵乘法的形式来表达变换后的像素位置映射关系。

那么,对于平移变换呢?平移变换表示的是位置变化的概念。如下图所示,一个图像矩形从中心点[x1,y1]平移到了中心点[x2,y2]处,整体大小和角度都没有变化。在x方向和y方向上分别平移了tx和ty大小。

显然:

     \[ x_{2} = x_{1} + t_{x} \] \[ y_{2} = x_{2} + t_{y} \]

这对于图像中的每一个点都是成立的。写成矩阵的形式就是:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \end{bmatrix} = \begin{bmatrix}   x_{1} \\   y_{1} \end{bmatrix} + \begin{bmatrix}   t_{x} \\   t_{y} \end{bmatrix} \]

我们再把前面的缩放变换和旋转变换的矩阵形式写出来:
缩放变换:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \end{bmatrix} = \begin{bmatrix}   k_{x} && 0 \\   0 && k_{y} \end{bmatrix} \begin{bmatrix}   x_{1} \\   y_{1} \end{bmatrix} \]

旋转变换:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \end{bmatrix} = \begin{bmatrix}   cos\theta && sin\theta \\   -sin\theta && cons\theta \end{bmatrix} \begin{bmatrix}   x_{1} \\   y_{1} \end{bmatrix} \]

我们注意到,缩放变换和旋转变换都可以表示成矩阵乘法的形式。实际上,图像的几何变换通常不是单一的,也就是说经常性的缩放、旋转、平移一起变换。例如先放大2倍,然后旋转45度,然后再缩小0.5倍。那么就可以表示成矩阵乘法串接的形式:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \end{bmatrix} = \begin{bmatrix}   0.5 && 0 \\   0 && 0.5 \end{bmatrix} \begin{bmatrix}   cos45 && -sin45 \\   sin45 && cos45 \end{bmatrix} \begin{bmatrix}   2 && 0 \\   0 && 2 \end{bmatrix} \begin{bmatrix}   x_{1} \\   y_{1} \end{bmatrix} \]

这样,不管有多少次变换,都可以用矩阵乘法来实现。但是平移变换呢?从前面看到,平移变换并不是矩阵乘法的形式,而是矩阵加法的形式!

那能不能把缩放变换、旋转变换、平移变换统一成矩阵乘法的形式呢,这样不管进行多少次变换,都可以表示成矩阵连乘的形式,将极大的方便计算和降低运算量。

这种方法就是“升维”,引入“齐次坐标”,将图像从平面2D坐标变成3D坐标。我们看看平移变换的矩阵形式:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \end{bmatrix} = \begin{bmatrix}   x_{1} \\   y_{1} \end{bmatrix} + \begin{bmatrix}   t_{x} \\   t_{y} \end{bmatrix} \]

将其升维,变成3维,上式就可以表示成:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \\   1 \end{bmatrix} = \begin{bmatrix}   1 && 0 && t_{x} \\   0 && 1 && t_{y} \\   0 && 0 && 1 \\ \end{bmatrix} + \begin{bmatrix}   x_{1} \\   y_{1} \\   1 \end{bmatrix} \]

这是个非常优美的地方,学习过矩阵乘法的同学可以算一下右边的式子,是否最终结果与前面是一样的。

这样,平移变换通过升维后的齐次坐标,也变成了矩阵乘法的形式。当然缩放变换和旋转变换的矩阵形式也得改一改,统一变成3维的形式。
缩放变换:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \\   1 \end{bmatrix} = \begin{bmatrix}   k_{x} && 0 && 0 \\   0 && k_{y} && 0 \\   0 && 0 && 1 \\ \end{bmatrix} + \begin{bmatrix}   x_{1} \\   y_{1} \\   1 \end{bmatrix} \]

旋转变换:

     \[ \begin{bmatrix}   x_{2} \\   y_{2} \\   1 \end{bmatrix} = \begin{bmatrix}   cos\theta && -sin\theta && 0 \\   sin\theta && cos\theta && 0 \\   0 && 0 && 1 \\ \end{bmatrix} + \begin{bmatrix}   x_{1} \\   y_{1} \\   1 \end{bmatrix} \]

终于统一了。以后所有的变换,不管怎样变换,变换多少次,都可以表示成一连串的矩阵相乘了,这是多么的方便。这就是引入齐次坐标的作用,把各种变换都统一了起来。

From:https://blog.csdn.net/saltriver/article/details/79680364

Over!

Run QEMU with hardware virtualization on macOS

在macOS上通过虚拟机运行其它操作系统,又不想用商业软件,那么开源的QEMU是一个比较好的选择。QEMU的功能支持还是比较全面的,除了功能以外,使用虚拟机软件的用户最关心的就是性能了,一个好消息是macOS 10.10+版本已经引人了硬件虚拟化支持框架,也就是Hypervisor.framework,另一个好消息是QEMU也已支持该框架,也就是hvf accelerator。

Requirements
1. macOS 10.10+
2. Macports

Issues
已经使用过的用户可能已经发现,QEMU使用hvf accelerator并开启多核是有问题的呀。的确,QEMU使用hvf accelerator以单核运行时没有问题,当使用-smp参数指定多核时,很大概率上虚拟机硬件初始化都完成不了就死机了。
不过,好消息是该问题也已经修复了,导致这个问题的原因是hvf accelerator代码设计没有考虑到虚拟机启动后所有hvf vcpu都在并行执行指令,其中包括硬件初始化的I/O模拟操作,多个CPU同时对同一硬件执行初始化显然是不行的。

Patch (已经提交上游社区,Review中,期望尽快合并)

Install QEMU

cd ~
git clone https://github.com/hevz/macports
sudo vim /opt/local/etc/macports/sources.conf
# Add local repositories
file:///Users/[YOUR USER NAME]/macports
rsync://rsync.macports.org/macports/release/tarballs/ports.tar [default]
cd ~/macports
portindex
sudo port install qemu

Run Arch Linux
1. 下载Arch Linux安装ISO镜像。
2. 创建一个虚拟机磁盘镜像。
3. 开始安装新的系统。
4. 启动安装后的系统。

mkdir ~/system/images
qemu-img create -f qcow2 ~/system/images/arch.qcow2 40G
 
qemu-system-x86_64 -no-user-config -nodefaults -show-cursor \
    -M pc-q35-3.1,accel=hvf,usb=off,vmport=off \
    -cpu host -smp 4,sockets=1,cores=2,threads=2 -m 4096 \
    -realtime mlock=off -rtc base=utc,driftfix=slew \
    -drive file=~/system/images/arch.qcow2,if=none,format=qcow2,id=disk0 \
    -device virtio-blk-pci,bus=pcie.0,addr=0x1,drive=disk0 \
    -netdev user,id=net0,hostfwd=tcp::2200-:22 \
    -device virtio-net-pci,netdev=net0,bus=pcie.0,addr=0x2 \
    -device virtio-keyboard-pci,bus=pcie.0,addr=0x3 \
    -device virtio-tablet-pci,bus=pcie.0,addr=0x4 \
    -device virtio-gpu-pci,bus=pcie.0,addr=0x5 \
    -cdrom ~/archlinux-2019.01.01-x86_64.iso -boot d

安装完成后,删除qemu-system-x86_64最后一行命令即可启动新系统。

Over!

Transparent proxy per application on Linux

This is a transparent proxy per app based on iptables + network classifier cgroup on Linux, and it’s more general than proxychains.

Build and install tproxy

git clone --recursive https://github.com/heiher/hev-socks5-tproxy
cd hev-socks5-tproxy
make
 
sudo cp bin/hev-socks5-tproxy /usr/local/bin/
sudo cp conf/main.ini /usr/local/etc/hev-socks5-tproxy.conf

Install systemd serivce

# /etc/systemd/system/hev-socks5-tproxy.service
[Unit]
Description=HevSocks5TProxy
 
[Service]
User=nobody
ExecStart=/usr/local/bin/hev-socks5-tproxy /usr/local/etc/hev-socks5-tproxy.conf
KillMode=process
Restart=always
LimitNOFILE=65536
 
[Install]
WantedBy=multi-user.target

Install tproxy wrapper

#!/bin/bash
# /usr/local/bin/tproxy
 
NET_CLS_DIR="/sys/fs/cgroup/net_cls/tproxy"
NET_CLS_ID=88
TP_TCP_PORT=1088
TP_DNS_PORT=5300
 
if [ ! -e ${NET_CLS_DIR} ]; then
	sudo sh -c "mkdir -p ${NET_CLS_DIR}; \
		chmod 0666 ${NET_CLS_DIR}/tasks; \
		echo ${NET_CLS_ID} > ${NET_CLS_DIR}/net_cls.classid; \
		iptables -t nat -D OUTPUT -p tcp \
			-m cgroup --cgroup ${NET_CLS_ID} \
			-j REDIRECT --to-ports ${TP_TCP_PORT}; \
		iptables -t nat -D OUTPUT -p udp --dport 53 \
			-m cgroup --cgroup ${NET_CLS_ID} \
			-j REDIRECT --to-ports ${TP_DNS_PORT}; \
		iptables -t nat -I OUTPUT -p tcp \
			-m cgroup --cgroup ${NET_CLS_ID} \
			-j REDIRECT --to-ports ${TP_TCP_PORT}; \
		iptables -t nat -I OUTPUT -p udp --dport 53 \
			-m cgroup --cgroup ${NET_CLS_ID} \
			-j REDIRECT --to-ports ${TP_DNS_PORT};" 2>&1 2> /dev/null
fi
 
echo $$ > ${NET_CLS_DIR}/tasks
 
exec "$@"

How to use?

tproxy COMMAND
 
# For example
tproxy wget http://xxx.com/xxx
tproxy makepkg

Over!

Dump VDSO via GDB

gdb /bin/bash
(gdb) b main
(gdb) r
(gdb) info proc map
Mapped address spaces:
          Start Addr           End Addr       Size     Offset objfile
      ...
      0x7ffff7fd1000     0x7ffff7fd3000     0x2000        0x0 [vdso]
      ...
(gdb) dump binary memory /tmp/vdso.so 0x7ffff7fd1000 0x7ffff7fd3000
(gdb) quit
file /tmp/vdso.so
/tmp/vdso.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=1a3fac101214fe3ecfb3788d4f8af3018f1f2667, stripped

Over!

Reordering on an Alpha processor

A very non-intuitive property of the Alpha processor is that it allows the following behavior:

Initially: p = & x, x = 1, y = 0

    Thread 1         Thread 2
--------------------------------
  y = 1         |    
  memoryBarrier |    i = *p
  p = & y       |
--------------------------------
Can result in: i = 0

This behavior means that the reader needs to perform a memory barrier in lazy initialization idioms (e.g., Double-checked locking) and creates issues for synchronization-free immutable objects (e.g., ensuring. that other threads see the correct value for fields of a String object).

Kourosh Gharachorloo wrote a note explaining how it can actually happen on an Alpha multiprocessor:
The anomalous behavior is currently only possible on a 21264-based system. And obviously you have to be using one of our multiprocessor servers. Finally, the chances that you actually see it are very low, yet it is possible.

Here is what has to happen for this behavior to show up. Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0. P1 does y=1 which causes an “invalidate y” to be sent to P2. This invalidate goes into the incoming “probe queue” of P2; as you will see, the problem arises because this invalidate could theoretically sit in the probe queue without doing an MB on P2. The invalidate is acknowledged right away at this point (i.e., you don’t wait for it to actually invalidate the copy in P2’s cache before sending the acknowledgment). Therefore, P1 can go through its MB. And it proceeds to do the write to p. Now P2 proceeds to read p. The reply for read p is allowed to bypass the probe queue on P2 on its incoming path (this allows replies/data to get back to the 21264 quickly without needing to wait for previous incoming probes to be serviced). Now, P2 can derefence P to read the old value of y that is sitting in its cache (the inval y in P2’s probe queue is still sitting there).

How does an MB on P2 fix this? The 21264 flushes its incoming probe queue (i.e., services any pending messages in there) at every MB. Hence, after the read of P, you do an MB which pulls in the inval to y for sure. And you can no longer see the old cached value for y.

Even though the above scenario is theoretically possible, the chances of observing a problem due to it are extremely minute. The reason is that even if you setup the caching properly, P2 will likely have ample opportunity to service the messages (i.e., inval) in its probe queue before it receives the data reply for “read p”. Nonetheless, if you get into a situation where you have placed many things in P2’s probe queue ahead of the inval to y, then it is possible that the reply to p comes back and bypasses this inval. It would be difficult for you to set up the scenario though and actually observe the anomaly.

The above addresses how current Alpha’s may violate what you have shown. Future Alpha’s can violate it due to other optimizations. One interesting optimization is value prediction.

From: http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html

Over!

Disable IBus embed preedit text via dbus-send

dbus-send --bus="`ibus address`" --print-reply \
    --dest=org.freedesktop.IBus \
    /org/freedesktop/IBus \
    org.freedesktop.DBus.Properties.Set \
    string:org.freedesktop.IBus string:EmbedPreeditText variant:boolean:false

Over!

Linux simple source policy routing

Dual network connections
eth0:
Address: 192.168.0.2
NetMask: 255.255.255.0
Gateway: 192.168.0.1

eth1:
Address: 192.168.1.2
NetMask: 255.255.255.0
Gateway: 192.168.1.1

Routing policy
* Transmit via eth0 when source address is 192.168.0.2
* Transmit via eth1 when source address is 192.168.1.2

Commands

# eth0
ifconfig eth0 192.168.0.2/24 up
ip rule add from 192.168.0.2 table 251
ip route add default via 192.168.0.1 dev eth0 src 192.168.0.2 table 251
 
# eth1
ifconfig eth1 192.168.1.2/24 up
ip rule add from 192.168.1.2 table 252
ip route add default via 192.168.1.1 dev eth1 src 192.168.1.2 table 252

Over!