Natural sort order is what we usually see in most file managers when browsing a list of numbered files, that it sorts the numerical part of the file name as a number instead of comparing it character by character. For instance:

Lexicographical sort Natural sort
1.txt 1.txt
10.txt 2.txt
100.txt 3.txt
101.txt 4.txt
102.txt 5.txt
103.txt 10.txt
104.txt 11.txt
105.txt 12.txt
11.txt 13.txt
12.txt 14.txt
13.txt 15.txt
14.txt 100.txt
15.txt 101.txt
2.txt 102.txt
3.txt 103.txt
4.txt 104.txt
5.txt 105.txt

Lexicographical sort can be easily implemented using String::compareToIgnoreCase, but it is not very acceptable for end users. However for natural sort, things is actually a little more complicated.


The Definition

There is a small Wikipedia article on Natural Sort Order, which mentioned the following definition for natural sort order:

Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are ordered as a single character.

However, there’s still some undefined behavior about this sort order when case-insensitivity is involved alongside treating numbers as a whole. In an article discussing natural sort order in C, the author mentioned the following case:

Name
Test1
tesT1
test1
tEst2
test2
test3

These string is listed in a reasonable way, however if you simply define the natural sorting to be sorting chunks of characters and numbers individually, the Test string have to be equal to test so that the ordering won’t be deterministic.

And there’s another case involving leading zeros:

Name
test1
test01
test001
test01a

Intuitively, things that are shorter should come before those longer ones, so equal numbers with less leading zeros should come before those with more. Furthermore, if there’s more text following the number, it should come after those without, thus the aforementioned leading zero comparison has a lower priority.

I didn’t find any standard for these corner cases, so I’m merely deciding on the most reasonable approach.

Various Implementations

There’s an article on CodingHorror and a StackOverflow question that referenced some existing implementations.

And here are some additional implementations that I found inside some battlefield applications:

But there’s some common issues in existing implementations:

  • Use of regular expression: The comparator is frequently evaluated during the sort, so performance is our concern and splitting on regular expressions is not what we expect under such conditions.
  • Memory allocation: Also due to the frequent invocation, we should avoid memory allocation (e.g. actually building those “chunks”), and this can be done by iteration over the two strings.
  • Unicode awareness: Unicode code points are not necessarily single chars (think of surrogates), so those code point related methods should be used instead of simple increment to advance the index of current “character”.
  • Locale awareness: Instead of c >= '0' && c <= '9', one should use Character.isDigit() and Character.digit() for getting numbers out of a character.
  • Correctness: Some implementations cannot handle the two aforementioned corner cases properly.
  • Coding style: Some implementations are simply not so readable.

My Implementation

So I wrote my own implementation with those issues in mind, and it basically iterates over the two string and handles consecutive digits together. Most of the code is self-explanatory and the comments can also describe the algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class NaturalOrderComparator implements Comparator<String> {

private static final int DIGIT_RADIX = 10;

@Override
public int compare(String string1, String string2) {
int start1 = 0;
int start2 = 0;
int leadingZeroCompareResult = 0;
while (start1 < string1.length() && start2 < string2.length()) {
int codePoint1 = string1.codePointAt(start1);
int codePoint2 = string2.codePointAt(start2);
// Check if both code points are digits.
if (!Character.isDigit(codePoint1) || !Character.isDigit(codePoint2)) {
if (!codePointEqualsIgnoreCase(codePoint1, codePoint2)) {
return codePointCompareToIgnoreCase(codePoint1, codePoint2);
}
start1 = string1.offsetByCodePoints(start1, 1);
start2 = string2.offsetByCodePoints(start2, 1);
continue;
}
// Get end of current number.
int end1 = start1;
do {
end1 = string1.offsetByCodePoints(end1, 1);
} while (end1 < string1.length() && Character.isDigit(string1.codePointAt(end1)));
int end2 = start2;
do {
end2 = string2.offsetByCodePoints(end2, 1);
} while (end2 < string2.length() && Character.isDigit(string2.codePointAt(end2)));
// Get start of current number without leading zeros.
int noLeadingZeroStart1 = start1;
while (noLeadingZeroStart1 < end1 && Character.digit(string1.codePointAt(
noLeadingZeroStart1), DIGIT_RADIX) == 0) {
noLeadingZeroStart1 = string1.offsetByCodePoints(noLeadingZeroStart1, 1);
}
int noLeadingZeroStart2 = start2;
while (noLeadingZeroStart2 < end2 && Character.digit(string2.codePointAt(
noLeadingZeroStart2), DIGIT_RADIX) == 0) {
noLeadingZeroStart2 = string2.offsetByCodePoints(noLeadingZeroStart2, 1);
}
// If the two lengths of numbers (without leading zeros) differ, the shorter one comes
// first.
int noLeadingZeroLength1 = string1.codePointCount(noLeadingZeroStart1, end1);
int noLeadingZeroLength2 = string2.codePointCount(noLeadingZeroStart2, end2);
if (noLeadingZeroLength1 != noLeadingZeroLength2) {
return noLeadingZeroLength1 - noLeadingZeroLength2;
}
// If any two digits starting from the first non-zero ones differs, the less one comes
// first.
for (int digitIndex1 = noLeadingZeroStart1, digitIndex2 = noLeadingZeroStart2;
digitIndex1 < end1; digitIndex1 = string1.offsetByCodePoints(digitIndex1, 1),
digitIndex2 = string2.offsetByCodePoints(digitIndex2, 1)) {
int digit1 = Character.digit(string1.codePointAt(digitIndex1), DIGIT_RADIX);
int digit2 = Character.digit(string2.codePointAt(digitIndex2), DIGIT_RADIX);
if (digit1 != digit2) {
return digit1 - digit2;
}
}
// If the two numbers are the same, the one with less leading zeros (shorter) comes
// first.
int leadingZeroLength1 = string1.codePointCount(start1, noLeadingZeroStart1);
int leadingZeroLength2 = string2.codePointCount(start2, noLeadingZeroStart2);
if (leadingZeroLength1 != leadingZeroLength2) {
if (leadingZeroCompareResult == 0) {
leadingZeroCompareResult = leadingZeroLength1 - leadingZeroLength2;
}
}
start1 = end1;
start2 = end2;
}
// If one of the two strings is exhausted first, it comes first.
int remainingLength1 = string1.codePointCount(start1, string1.length());
int remainingLength2 = string2.codePointCount(start2, string2.length());
if (remainingLength1 != remainingLength2) {
return remainingLength1 - remainingLength2;
}
// The one with less leading zeros (shorter) comes first if others are the same.
if (leadingZeroCompareResult != 0) {
return leadingZeroCompareResult;
}
// Fall back to plain comparison.
return string1.compareTo(string2);
}

// @see String#regionMatches(boolean, int, String, int, int)
private static boolean codePointEqualsIgnoreCase(int codePoint1, int codePoint2) {
codePoint1 = Character.toUpperCase(codePoint1);
codePoint2 = Character.toUpperCase(codePoint2);
if (codePoint1 == codePoint2) {
return true;
}
codePoint1 = Character.toLowerCase(codePoint1);
codePoint2 = Character.toLowerCase(codePoint2);
return codePoint1 == codePoint2;
}

// @see String.CaseInsensitiveComparator#compare(String, String)
private static int codePointCompareToIgnoreCase(int codePoint1, int codePoint2) {
if (codePoint1 != codePoint2) {
codePoint1 = Character.toUpperCase(codePoint1);
codePoint2 = Character.toUpperCase(codePoint2);
if (codePoint1 != codePoint2) {
codePoint1 = Character.toUpperCase(codePoint1);
codePoint2 = Character.toUpperCase(codePoint2);
if (codePoint1 != codePoint2) {
return codePoint1 - codePoint2;
}
}
}
return 0;
}
}

The code is also available as a GitHub gist and is licensed under the Apache 2.0 license.

Further Considerations

In fact, to account for Unicode’s compatibility decomposition, canonical composition and case folding, an ICU Normalizer should be used with mode NFKC_Casefold. However, since the ICU package is not available on Android until Android Oreo, and the JDK implementation didn’t account for such level of correctness, I’m currently leaving it out and you can trivially add it by applying the normalization before comparison.

For years OpenWeather has been my favorite GNOME extension for quick and beautiful weather information. However today when I looked at my top bar again for weather, I had the impression as if something is missing:

And this is what it used to be like:

My degree Celsius symbol is missing!


Finding the culprit

The first thing I thought was, is this specific to OpenWeather? And I was surprised to find out that when I googled “degree Celsius symbol”, the °C as U+00B0 ° degree sign plus U+0043 C latin capital letter c is present, while ℃ as U+2103 ℃ degree celsius is simply empty. However a <span> with font-family: serif on Wikipedia showed the symbol correctly, so this must be a font/fontconfig issue.

And I lessed my own fontconfig configuration with /etc/fonts/local.conf:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
<match>
<test name="family"><string>sans-serif</string></test>
<edit name="family" mode="prepend" binding="strong">
<string>WenQuanYi Micro Hei</string>
<string>WenQuanYi Zen Hei</string>
<string>WenQuanYi Bitmap Song</string>
<string>DejaVu Sans</string>
<string>Noto Color Emoji</string>
</edit>
</match>
<match>
<test name="family"><string>serif</string></test>
<edit name="family" mode="prepend" binding="strong">
<string>DejaVu Serif</string>
<string>WenQuanYi Bitmap Song</string>
<string>WenQuanYi Zen Hei Sharp</string>
<string>AR PL UMing CN</string>
<string>AR PL UMing TW</string>
<string>AR PL New Sung</string>
<string>Noto Color Emoji</string>
</edit>
</match>
<match>
<test name="family"><string>monospace</string></test>
<edit name="family" mode="prepend" binding="strong">
<string>WenQuanYi Micro Hei Mono</string>
<string>WenQuanYi Zen Hei Mono</string>
<string>WenQuanYi Bitmap Song</string>
<string>DejaVu Sans Mono</string>
<string>Noto Color Emoji</string>
</edit>
</match>
</fontconfig>

So the different order of font families in sans-serif and serif might be the issue. I googled a while for finding out the font selected by fontconfig for a glyph, and found an article suggesting the use of FC_DEBUG and pango-view:

1
FC_DEBUG=4 pango-view -q --font='<YOUR_FONT_FAMILY>' -t '<YOUR_CHARACTER>' 2>&1 | grep -o 'family:"[^"]+' | cut -c 10- | tail -n 1

The latter part basically filters out the last printed family name from the tedious debug output. And when I run this for my degree Celsius symbol (), I found:

What’s wrong with WenQuanYi Micro Hei? I’ve been using it for years, and now it’s giving me nothing for degree Celsius symbol? And why did fontconfig ever choose it seemed to have no such glyph?

Confused by this I opened my wqy-microhei.ttc with FontForge, and was again surprised to find out that my WenQuanYi Micro Hei is providing an empty glyph (instead of nothing) for certain codepoints!

This is crazy, and I’m left wondering how my degree Celsius symbol ever worked in the past few years.

Finding the way to fix it

There must be some configuration that allow me to blacklist certain glyphs in a font. And after another round of digging around, I found some interesting results.

The first one is a bug on fontconfig Bugzilla which requested such support back in 2006 and was marked fixed in 2011. Feeling excited, I scrolled down and found a single line of comment from the dev:

This is fixed in master with target=scan charset editing.

After all the hard work, why didn’t he or she celebrate the moment of closing this bug with a more detailed explanation, or at least a helpful pointer? Even after reading though man fonts-conf, I found nothing describing how I can edit the charset of a font family. After all, the <charset> element says it must contain one or more integer, however the whole charset normally contains a huge amount of hexadecimal integers.

So I searched harder and found another answer on StackOverflow. It suggested an undocumented way of configuration that’s mentioned somewhere in a RedHat bug thread, which was its only appearance on the whole Internet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<match target="scan">
<test name="family" compare="not_eq">
<string>VL Gothic</string>
</test>
<edit name="charset" mode="assign">
<minus>
<name>charset</name>
<range>
<int>0x0021</int>
<int>0x00FF</int>
</range>
</minus>
</edit>
</match>

This is just what i wanted! So I happily applied this to my mischievous WenQuanYi Micro Hei, changing the compare to "eq" and setting the range to include 0x2103 (My precious degree Celsius symbol). Finally, sudo fc-cache -f && fc-cache -f! [sigh of relief]

Nope.

This could have worked, in some time of the history, but is not working for now, on my latest Arch Linux installation.

No.

But wait. I did saw something mentioning, we have a <charset> element and it must contain some integers? So I started to coin my own solution (You should also do the same for WenQuanYi Micro Hei Mono):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<match target="scan">
<test name="family">
<string>WenQuanYi Micro Hei</string>
</test>
<edit name="charset">
<minus>
<name>charset</name>
<charset>
<int>0x2103</int>
<int>0x2109</int>
<int>0x212B</int>
<int>0x2164</int>
<int>0x2169</int>
</charset>
</minus>
</edit>
</match>

sudo fc-cache -f && fc-cache -f, pango-view again to confirm, and Alt+F2 r to restart my GNOME shell. It worked! After all these hours, my degree Celsius symbol is back and alive again!

A final note

The above solution is only a workaround, and to actually fix this, The Wenquanyi Micro Hei font itself should be patched. In fact this was what I first tried when I surprisingly found out those empty glyphs.

However, when I went to wenq.org, there latest update was posted in late 2011 (We are in 2018 now), and their forum is giving me a blank page with certain resources returning 404. Their SourceForge issue tracker is also unattended for years with that notorious hangul advance bug still open. Sadly, the whole project seems dead. So I decided to work around instead of fixing this.

And one sentence I encountered during my search kept lingering in my mind:

When you gaze long into fontconfig, fontconfig also gazes into you.

Update: With another link on their official website, I was able to find their real bug tracker and this bug, and a similar bug. The dev said it’s fixed, but maybe some recent fontconfig or freetype changes brought it back. Maybe some day I should fork it and try to actually fix these bugs.

And according to the dev’s comment, those glyphs existed in Droid Sans Fallback, so a proper fix to my configuration should also include adding Droid Sans Fallback to the sans-serif and monospace families, right below the WenQuanYi Micro Hei entry.

前言

JavaScript 是一门灵活的动态语言,在实现应用功能时十分易用。最近有写作图形界面程序的需要,又比较喜爱 GTK+ 3 的设计,因此想到可以尝试使用 JavaScript 来完成任务。

选择运行时

首选的运行时当然是 node,因为它有着良好的 ES2015 特性支持,并且可以方便地使用 npm 管理的模块。在经过一番搜索之后,我找到了 WebReflection/node-gtk 这个项目,却发现它无法使用 node-gyp 在我的 Arch Linux 上进行编译。另一个 [creationix/node-gir] 提供了对 GObject Introspection 的绑定,但是在它的 README 中写明了有 bug 和内存管理等问题,看上去也难以令人满意。

因此,我选择了使用 GJS 作为运行时。虽然没有 node 的 ES2015 支持和使用不同模块的便利,但对于使用 GObject Introspection 的绑定而言足够可靠。

编写应用程序

GNOME 官方提供了 一个简单的 GJS 程序示例,可以按照它的架构进行编程。

文档

技巧

通过构造器设置属性

Gtk.Widget 的所有属性均可以通过向构造器传入的 Object 进行设置,而可用的属性可以通过运行 gtk3-widget-factory,然后启用 GtkInspector 来查看和实验。

布局

可以一直使用 Gtk.Grid 进行布局,它的功能类似于 Android 中的 LinearLayout。可以设置它的 border_widthrow_spacingcolumn_spacing 来控制留白,以及设置 expandhexpandvexpand 控制大小。通过调用(继承自 Gtk.Container 并经过覆盖)add() 方法即可按顺序添加子控件,不需要使用 attach() 那样复杂的功能。

设置 CSS Class

例如给 Gtk.Button 添加 suggested-action CSS 类使其变蓝:

1
button.get_style_context().add_class('suggested-action');

控件杂项

Gtk.Entry 相当于 Android 中的 EditText。可以通过设置 width_char 来修改 Gtk.Entry 的最小大小。

Gtk.Widigetsensitive 属性相当于 Android 中的 android:enabled

结语

Gjs 使得我们可以使用灵活的 JavaScript 编写美观的原生程序,总体来说体验是很好的。

我把自己编写的一个小程序放在了 GitHub Gist,可以作为参考。

Gjs 应用程序 OpticalSystem

最后,在编写这篇文章时,我找到了另一个 结合了 Gjs、NPM 和 Babel 的示例项目,读者也可以参考它进行编程。

前言

临近毕设,学院里提供了毕业设计报告的 LaTeX 模板,于是决定离开简单的 Markdown ,开始使用 LaTeX 进行写作。以下就是我使用过程中的一些记录。

样例项目

我对学院提供的旧 LaTeX 模板进行了较多的修改,使其符合了学院方面的最新格式要求,并且修复了设置字号时行间距不正确等等错误,可以直接使用或者用于参考学习:

浙江大学计算机科学与技术、软件工程专业本科毕业设计开题报告 LaTeX 模板

其中的 install-fonts.sh 可以用于从 Windows 分区获取需要的字体并进行安装。

安装 LaTeX

在 Arch Linux 上安装 LaTeX(TeXLive)较为简单,可以参考 Arch Wiki 安装对应的软件包。

也可以直接执行以下命令进行安装,这样基本不会在使用时遇到无法找到常用宏包的情况。

1
sudo pacman -S texlive-most texlive-langchinese

构建文档

xeCJK 是提供 LaTeX 中文支持的宏包,并且依赖于 XeLaTeX,因此,我们需要使用 xelatex 命令进行构建。

LaTeX 在构建交叉索引时需要多次运行,才能最终解析所有的引用,并且期间需要 BibTeX 对参考文献数据库进行处理。因此,一般的手动构建命令是:

1
2
3
4
xelatex main
bibtex main
xelatex main
xelatex main

不同于部分网页上给出的示例,这些命令都可以接受不带后缀名的参数,并且有时写出后缀名可能会阻碍多文件等情况下的正确构建。

对于子目录和多文件使用引用的情况,在主文件中应该使用 include 而非 input,否则会需要其他处理。

为了简化构建步骤,实际上应当使用 mklatex,它会根据需要自动调用各种命令。因此之前的手动构建步骤可以被以下命令替代:

1
mklatex -xelatex main

了解 LaTeX 和解决问题

LaTeX 有很多历史问题带来的不同,也有多重相似但不同的工具选择,因此网上提供的解决方案不一定可以工作,需要自己试验。

可以通过 ShareLaTeX 提供的文档 获得对 LaTeX 的初步了解。但是,这份文档中提到的引用等高级特性的使用可能与我们的方式不同。

推荐使用 TeX – LaTeX Stack Exchange 作为解决问题时的主要信息来源。

可以通过 texdef 命令查看 LaTeX 中命令的定义。例如:

1
texdef -t xelatex -s -c csbachelor thebibliography

零碎知识

  • \:换行,不新建段落。可选参数可以控制空白长度。
  • par:创建段落。parskipparindent 将生效。部分命令需要对段落才能生效,因此可能需要在最后一段文字最后加上 par
  • :一个空格。
  • &:一个 NBSP,不会被分行打断,常用于类似 图~1 这样的场景。
  • hspace{1em}:一个 1 em 长度的空格。
  • renewcommand:修改命令定义。
  • setlength:修改长度变量。
  • setcounter:修改计数器。

结语

LaTeX 十分强大,并且作为纯文本格式依然比 Word 文档等更加清晰、明确、可靠。但是,整个 LaTeX 环境也正因为它的高自由度和复杂,在许多方面缺乏一致性,这给使用者带来了不少困难。

总体来说,在经过大量的学习和尝试之后,我依然认为 LaTeX 是一个优秀的排版工具。它可以让使用者在一次配置之后获得强大的功能,并且在写作过程中始终保持工作在纯文本层面上。

关于各种命令和功能的常见用法,读者可以继续参考我在文章开头提到过的 报告模板,我也会在写作毕业设计论文时继续更新。

前言

因为计算机图形学课程作业的需要,我在使用过 OpenGL 的基础上学习了使用 WebGL 进行二维图形渲染。

WebGL 拥有与 OpenGL ES 相似的 API(前者基于后者),但与 OpenGL 相比,两者缺少基础图形的渲染管线,而是需要手写 shader 进行渲染。

基础

请阅读 WebGL Fundamentals 以获得对于 WebGL 的大体了解。

Shader

在 WebGL 中需要两种 shader 进行渲染。第一种是 vertex shader,负责对顶点进行变换,例如将像素坐标映射到 clip space。而第二种是 fragment shader,负责对像素点进行着色。

Shader 可以有两种参数。第一种是 attribute,在每次调用中不同,例如当前顶点的位置;第二种是 uniform,在渲染过程中共享,例如渲染的变换矩阵。

以下是两个实用的简单 2D shader:

Vertex shader:

1
2
3
4
5
6
7
attribute vec2 a_position;
uniform mat3 u_transformation;
void main() {
gl_Position = vec4((u_transformation * vec3(a_position, 1)).xy, 0, 1);
}

Fragment shader:

1
2
3
4
5
6
7
precision mediump float;
uniform vec4 u_color;
void main() {
gl_FragColor = u_color;
}

初始化

以下是我的一些工具函数,参考了 WebGL Boilerplate 和一部分 WebGL – Less Code, More Fun

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function createAndCompileShader(gl, id) {
var element = document.getElementById(id);
var type = null;
switch (element.type) {
case 'x-shader/x-vertex':
type = gl.VERTEX_SHADER;
break;
case 'x-shader/x-fragment':
type = gl.FRAGMENT_SHADER;
break;
default:
throw 'Unknown shader type:' + element.type;
}
var source = element.textContent;
var shader = gl.createShader(type);
gl.shaderSource(shader, source);
gl.compileShader(shader);
if (!gl.getShaderParameter(shader, gl.COMPILE_STATUS)) {
throw 'Error compiling shader:' + gl.getShaderInfoLog(shader);
}
return shader;
}
function createAndLinkProgram(gl, vertexShaderId, fragmentShaderId) {
var program = gl.createProgram();
gl.attachShader(program, createAndCompileShader(gl, vertexShaderId));
gl.attachShader(program, createAndCompileShader(gl, fragmentShaderId));
gl.linkProgram(program);
if (!gl.getProgramParameter(program, gl.LINK_STATUS)) {
throw 'Error linking program:' + gl.getProgramInfoLog(program);
}
return program;
}

提供数据

以下是我自己写作的一些工具函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @param {[float]} value
*/
function setUniformFv(gl, program, name, value) {
gl['uniform' + value.length + 'fv'](gl.getUniformLocation(program, name), value);
}
/**
* @param {string} color '#RRGGBB'
* @param {float=} alpha in [0, 1]
*/
function setUniformColor(gl, program, name, color, alpha) {
if (!/^#[0-9A-Fa-f]{6}$/.test(color)) {
throw 'Invalid color:' + color;
}
setUniformFv(gl, program, name, [
parseInt(color.substr(1, 2), 16) / 0xff,
parseInt(color.substr(3, 2), 16) / 0xff,
parseInt(color.substr(5, 2), 16) / 0xff,
alpha || 1
]);
}
function setUniformMatrix(gl, program, name, value) {
gl['uniformMatrix' + Math.sqrt(value.length) + 'fv'](gl.getUniformLocation(program, name), false, value);
}
/**
* @param {[[float]]} value
*/
function setAttributeArrayFva(gl, program, name, value) {
var buffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
var data = new Float32Array(Array.prototype.concat.apply([], value));
gl.bufferData(gl.ARRAY_BUFFER, data, gl.STATIC_DRAW);
var location = gl.getAttribLocation(program, name);
gl.enableVertexAttribArray(location);
var size = value[0].length;
gl.vertexAttribPointer(location, size, gl.FLOAT, false, 0, 0);
}

变换矩阵

以下代码参考了 WebGL 2D TranslationWebGL Orthographic 3D。需要注意的是,原教程的代码中有部分矩阵错误地以行优先而非列有限的方式进行表示或运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
function makeIdentityMatrix() {
return [
1, 0, 0,
0, 1, 0,
0, 0, 1
];
}
function makeTranslationMatrix(tx, ty) {
return [
1, 0, 0,
0, 1, 0,
tx, ty, 1
];
}
function makeScalingMatrix(sx, sy) {
return [
sx, 0, 0,
0, sy, 0,
0, 0, 1
];
}
function degreeToRadian(angle) {
return angle / 180 * Math.PI;
}
function makeRotationMatrix(angle) {
angle = degreeToRadian(angle);
var cosa = Math.cos(angle);
var sina = Math.sin(angle);
return [
cosa, sina, 0,
-sina, cosa, 0,
0, 0, 1
];
}
function makeSkewXMatrix(angle) {
angle = degreeToRadian(angle);
var tana = Math.tan(angle);
return [
1, 0, 0,
tana, 1, 0,
0, 0, 1
];
}
function makeSkewYMatrix(angle) {
angle = degreeToRadian(angle);
var tana = Math.tan(angle);
return [
1, tana, 0,
0, 1, 0,
0, 0, 1
];
}
function makeProjectionMatrix(width, height) {
return [
2 / width, 0, 0,
0, -2 / height, 0,
-1, 1, 1
];
}
function multiplyMatrix(a, b) {
// A cdot B = (B^T cdot A^T)^T
var a00 = a[0], a01 = a[1], a02 = a[2];
var a10 = a[3], a11 = a[4], a12 = a[5];
var a20 = a[6], a21 = a[7], a22 = a[8];
var b00 = b[0], b01 = b[1], b02 = b[2];
var b10 = b[3], b11 = b[4], b12 = b[5];
var b20 = b[6], b21 = b[7], b22 = b[8];
return [
b00 * a00 + b01 * a10 + b02 * a20,
b00 * a01 + b01 * a11 + b02 * a21,
b00 * a02 + b01 * a12 + b02 * a22,
b10 * a00 + b11 * a10 + b12 * a20,
b10 * a01 + b11 * a11 + b12 * a21,
b10 * a02 + b11 * a12 + b12 * a22,
b20 * a00 + b21 * a10 + b22 * a20,
b20 * a01 + b21 * a11 + b22 * a21,
b20 * a02 + b21 * a12 + b22 * a22
];
}

近似于 OpenGL 的 API 封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
var _gl = null;
var _program = null;
function initialize(gl, program) {
_gl = gl;
_program = program;
}
function setColor(color, alpha) {
setUniformColor(_gl, _program, 'u_color', color, alpha);
}
var _transformations = [];
function getTransformation() {
return _transformations[_transformations.length - 1];
}
function _setTransformation(transformation) {
setUniformMatrix(_gl, _program, 'u_transformation', transformation);
}
function setTransformation(transformation) {
_setTransformation(transformation);
_transformations = [transformation];
}
function pushTransformation(transformation) {
transformation = multiplyMatrix(getTransformation(), transformation);
_setTransformation(transformation);
_transformations.push(transformation);
}
function popTransformation() {
_transformations.pop();
_setTransformation(getTransformation());
}
function drawTriangles(positions) {
setAttributeArrayFva(_gl, _program, 'a_position', positions);
_gl.drawArrays(_gl.TRIANGLES, 0, positions.length);
}
function drawRectangle(x, y, width, height) {
var x1 = x;
var y1= y;
var x2 = x + width;
var y2 = y + height;
drawTriangles([
[x1, y1],
[x2, y1],
[x1, y2],
[x1, y2],
[x2, y1],
[x2, y2]
]);
}

绘制和应对大小改变

以下代码参考了 WebGL Resizing the CanvasWebGL Anti-Patterns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function draw(gl) {
gl.viewport(0, 0, gl.drawingBufferWidth, gl.drawingBufferHeight);
gl.clearColor(0xde / 0xff, 0x29 / 0xff, 0x10 / 0xff, 0xff / 0xff);
gl.clear(gl.COLOR_BUFFER_BIT);
var program = createAndLinkProgram(gl, 'vertex-shader', 'fragment-shader');
gl.useProgram(program);
initialize(gl, program);
setColor('#ffdd00');
setTransformation(makeProjectionMatrix(1000, 800));
// Draw here.
gl.flush();
}
function main() {
var canvas = document.getElementById('canvas');
var webgl = canvas.getContext('webgl') || canvas.getContext('experimental-webgl');
if (!webgl) {
alert("Error initializing WebGL. Your browser may not support it.");
return;
}
var needToDraw = true;
function resizeAndDraw() {
var resized = canvas.width !== canvas.clientWidth || canvas.height !== canvas.clientWidth * 0.8;
if (resized) {
canvas.width = canvas.clientWidth;
canvas.height = canvas.clientWidth * 0.8;
}
if (resized || needToDraw) {
needToDraw = false;
draw(webgl);
}
requestAnimationFrame(resizeAndDraw);
}
requestAnimationFrame(resizeAndDraw);
}
main();

结语

作为一个复杂度适中的示例,我的作业代码可以在 这里 看到。

前言

Reveal.js 是一个美观实用 HTML 演示文稿框架,只需要你决定内容,就可以方便地产出外观优雅的演示文稿。你可以在线查看 Reveal.js 的 Demo

为了分享已经制作好的演示文稿,可以使用 GitHub Pages 进行部署,同时也能够不用安装依赖地开启演讲者视图。以下是我建立 slides.zhanghai.me 的过程。

基本

为了建立一个 GitHub Pages 站点,我们需要准备以下一些文件:

  • 404.html:GitHub Pages 将使用此页面作为默认 404 页面的替代,一般可以换成一个符合自己站点风格的页面。
  • CNAME:对于绑定自定义域名的 GitHub Pages,可以使用这个文件指定自己的自定义域名。
  • .nojekyll:我们的站点不需要 Jekyll 的特性干预,因此将它关闭来避免可能的问题。

然后在 GitHub 上建立仓库,执行以下的命令:

1
2
3
4
5
6
7
git init
# 将默认的分支名 master 改为 gh-pages
git symbolic-ref HEAD refs/heads/gh-pages
git commit -am 'Initial commit.'
# 将 your/repo/origin 替换为你的仓库地址
git remote add origin your/repo/origin
git push --set-upstream origin gh-pages

当然,使用自定义域名的话还要配置一下 DNS 记录。

演示文稿

为了部署 Reveal.js 的演示文稿,可以利用 Git 的 Submodule 来完成对 Reveal.js 项目本身的引用。如此以来,我们的站点项目的 Git 仓库就不用跟踪 Reveal.js 中各个文件的状态,又可以记住所引用的 Reveal.js 仓库当时的版本(Commit SHA1)。

比较幸运的是,GitHub Pages 的构建过程是可以支持 Submodule 的。需要注意的是,Submodule 的仓库地址必须采用 https 而非 ssh 协议(否则会收到构建失败的邮件通知)。以下是将 Reveal.js 作为 Submodule 引入的命令:

1
git submodule add https://github.com/hakimel/reveal.js.git

之后将你的 index.html 中对于 Reveal.js 文件的应用都加上 reveal.js/ 的目录前缀即可。

其他详情可以参考我的站点仓库 DreaminginCodeZH/slides.zhanghai.me

结语

Reveal.js 是一个易用而优雅的 HTML 演示文稿框架,借助于它,我已经多年没有用过 PowerPoint 了。至于利用 GitHub Pages 将它放置在网页端,则可以在免运维的情况下可靠地分享自己的演示文稿,同时也可以不用安装大量 npm 依赖来开启演讲者视图,算是一个简单又有用的小技巧。

因此,将我的配置过程和结果记录在此,希望能对他人有所帮助。

前言

Travis CI 是 GitHub 上开源项目采用持续集成的常见选择。为了给 豆芽 提供持续集成版本用于公开测试,我配置了 Travis CI,并自己编写了脚本将构建结果发布到另一个空项目的 Release 中,并将其间的过程和遇到的问题记录于此。

Travis CI 构建 Android 项目的时间较长,因此调试配置时十分耗时。希望我的经验能对他人有所帮助。

Travis CI

Travis CI 分为免费版(travis-ci.org)和付费版(travis-ci.com),两者之间没有相互的链接或说明,第一次配置时容易混淆。开源项目选择免费版即可。配置过程可以参考官方的 Getting StartedAndroid 项目配置

关于 Android 项目有一些较为微妙的配置问题,我自己调试并查阅了一些 Issue 方才解决。

  1. 为了能够找到并下载最新的 Build Tools,需要启用最新版本的 Tools(- tools)。
  2. Lint 过程中如果 Platform Tools 版本低于 SDK 版本则会报错,需要启用最新版本的 Platform Tools(-platform-tools)。
  3. 为了能够找到并下载最新的 Platform Tools,需要已有最新的 Tools,因此与官方给出的样例不同,需要将 - tools 放置在 - platform-tools 之前。

因此我的 Android 部分最终配置如下:

1
android:
  components:
    - tools
    - platform-tools
    - build-tools-24.0.1
    - android-24
    - extra-android-m2repository

详细配置可以参考我的 .travis.yml

启用构建缓存

Gradle 是一个为缓存优化过的工具,因此官方也提供了相应的 开启缓存的方法

1
before_cache:
  - rm -f $HOME/.gradle/caches/modules-2/modules-2.lock
cache:
  directories:
    - $HOME/.gradle/caches/
    - $HOME/.gradle/wrapper/

应用签名

为了给 CI 版本的 APK 签名,需要提供相应的 keystore 和密码。Travis CI 提供了 在设置中定义环境变量 的方式来传递低敏感级的信息。

基于以上文档和一些搜索结果,并参考过 Shadowsocks-Android 的配置方式,我将我的签名配置编写为了从 signing.properties、环境变量、终端输入三个层级进行获取的方式。

以下是我的 signing.gradle

1
2
3
4
5
6
7
8
9
10
11
12
android {
signingConfigs {
release {
Properties signingProperties = new Properties()
signingProperties.load(rootProject.file("signing.properties").newDataInputStream())
storeFile rootProject.file(signingProperties.get("storeFile"))
storePassword signingProperties.get("storePassword") ?: System.getenv("STORE_PASSWORD") ?: System.console()?.readLine("nStore password:")
keyAlias signingProperties.get("keyAlias")
keyPassword signingProperties.get("keyPassword") ?: System.getenv("KEY_PASSWORD") ?: System.console()?.readLine("nKey password:")
}
}
}

在 Android Studio 中进行 Gradle 同步时,System.console() 返回 null,因而密码均为 null,不会中断同步过程,也不影响调试版本的构建。

我创建了 signing.propertiessigning.properties.travis 两个文件,在前者中填写 keystore 的路径并加入 .gitignore,而将后者在 .travis.ymlbefore_script 中复制为 signing.properties

而在 Travis CI 的设置中,添加 STORE_PASSWORDKEY_PASSWORD 两个环境变量即可。建议在环境变量值的两端加上单引号以避免特殊字符被 shell 错误处理。

获取版本信息

直接在 .travis.yml 中调用 git describegit log 等命令是无法成功的,因为 Travis CI 采用了 git clone --depth=50 来进行 clone。相应地,需要先执行 git fetch --unshallow 来完成 clone。

我采用了 语义化版本(Semver)来命名版本。因此,我的版本名称采用了如下方式获取:

1
version="$(git describe --long --tags | sed's/^v//;s/-([0-9]+)-g([0-9a-f]+)/+1.2/')"

例如,在名为 1.0.0-alpha 的 tag 后第 227 次短哈希值为 886f8ce 的 commit,对应的版本名即为 1.0.0-alpha.1+227.886f8ce

然后使用 sed -i 's/versionName .*/versionName "'"${version}"'"/' app/build.gradle 即可更新 build.gradle 中的 versionName 字段。

上传至 Release

GitHub 提供了在 Release 中上传二进制构建输出的功能。然而,如果直接在项目仓库中为每次 commit 添加 Release(和相应的 tag)则未免过于杂乱,因此我选择了新建 一个只有 README 的仓库,并将所有持续集成版本的 Release 创建在此仓库中。

为了实现此功能,我选择了通过 curl 调用 GitHub API 的方式来完成。经过查阅文档和大量的调试,我的脚本最终是如下编写的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/bin/bash

set -e

repo="$1"
shift
echo "Repo: ${repo}" >&2

version="$1"
shift
echo "Version: ${version}" >&2

tag="v${version}"
echo "Tag: ${tag}" >&2

body="$1"
shift
echo "Body: ${body}" >&2

# Get old release by tag
echo "Getting old release by tag..." >&2
response="$(curl -H"Authorization: token ${GITHUB_ACCESS_TOKEN}""https://api.github.com/repos/${repo}/releases/tags/${tag}")"
echo "${response}" >&2
old_release_id="$(echo "${response}" | jq -r '.id')"

if [["${old_release_id}" != "null" ]]; then

# Delete old release
echo "Deleting old release..." >&2
response="$(curl -X 'DELETE' -H "Authorization: token ${GITHUB_ACCESS_TOKEN}" "https://api.github.com/repos/${repo}/releases/${old_release_id}")"
echo "${response}" >&2
fi

# Create release
echo "Creating release..." >&2
response="$(curl -H "Authorization: token ${GITHUB_ACCESS_TOKEN}" -H 'Content-Type: application/json' --data "{ "tag_name": $(echo -n"${tag}"| jq -s -R -r @json), "name": $(echo -n"${tag}"| jq -s -R -r @json), "body": $(echo -n"${body}"| jq -s -R -r @json) }" "https://api.github.com/repos/${repo}/releases")"
echo"${response}">&2
upload_url="$(echo "${response}" | jq -r '.upload_url' | sed 's/{?name,label}$//g')"
echo"Upload url: ${upload_url}">&2

for file in"$@"; do
# Upload file
echo"Uploading file: ${file}">&2
name="$(basename "${file}")"
response="$(curl -H "Authorization: token ${GITHUB_ACCESS_TOKEN}" -H "Content-Type: $(file -b --mime-type"${file}")" --data-binary "@${file}" "${upload_url}?name=$(echo -n"${name}"| jq -s -R -r @uri)")"
echo"${response}">&2
done

而设置 GITHUB_ACCESS_TOKEN 环境变量后的用法则如:

1
./upload-to-releases.sh 'DreaminginCodeZH/DouyaCiBuilds' "${version}" "${description}" "douya-ci-${version}.apk"

其他

如果无法确定错误原因,就多加些 echo 或者 cat 吧。

如果希望在 Lint 失败时查看输出,可以在 after_failure 中加入 cat app/build/outputs/lint-results-*.html

我所采用的配置都可以在 豆芽 中找到。

结语

为 Android 项目使用 Travis CI 的过程还算简单,但是也有一些微妙的问题需要解决,这令我花费了不少时间。而将每次的构建输出上传至另一个仓库的 Release 则是我考虑了一段时间后得出的方案,之前没见到过这种方式,用 curl 调用 GitHub API 也是第一次,同时再次感受到了 bash 的得心应手,总体上是一次十分有趣的体验。

因此,将我的配置过程和结果记录在此,希望对其他开发者有所帮助。

前言

这是我在大学修习逻辑与计算机设计基础、计算机组成和计算机体系结构三门硬件课的过程中积累的 Verilog 笔记。

Verilog 是一门主要用于逻辑电路设计的硬件描述语言。语言标准主要有 Verilog-1995Verilog-2001 两个版本,建议在创建工程时选择 Verilog-2001 标准以支持更多实用的语法。

虽然 Verilog 的语法与 C 相似,但是二者是面向各自的目标硬件设计的。Verilog 是一门面向逻辑电路的具体实现而设计的语言(正如 C 在某种程度上是面向汇编等底层实现的),因此写作 Verilog 时不可以将 C 等编程语言的思维方式代入,而是要始终清晰地思考正在编写的代码将能够综合成怎样的逻辑电路实现——如果可以,那么大多能够写出在字面和实现上都优雅的代码;如果不行,那么综合时大概也会报错或消耗大量资源,此时则应该考虑调整思路。

手册

Verilog 的标准文档 IEEE 1364-2001 在网络上可以找到下载,但相比之下,这份标准还是稍显冗长或不够友好。而在标准文档之外,Xilinx ISE 的 XST 综合器也提供了实现文档,并且其中包含了许多 Verilog 语法的实用描述,因此可以作为一本更加友好的手册进行查阅。

XST User Guide for Virtex-6, Spartan-6, and 7 Series Devices

以及这里还有一份简单的非官方 Verilog-2001 手册:

Verilog HDL Quick Reference Guide

指南

在本文草稿的同时,我的某位同学也完成了一份 Verilog 指南。指南十分详尽而实用,因此希望读者先行阅读。

Verilog General Guide

重复(Replication)

在 Verilog 中,你可以使用 {COUNT{singal}} 将指定的信号重复数次后连接。

例如,想要写一个 32 位 0/1 相见的字面量,不需要写出 32'b01010101010101010101010101010101,而是写 {16{2'b01}} 即可简洁而直观地完成。

另一个例子是 16 位到 32 位的符号扩展,也可以用 {16{signal[15]}, signal[15:0]} 来完成。

参数定义:parameter, localparam, `define

Verilog 提供了三种定义“常量”的方式。

parameter 是可以由模块外部改变的参数。除了在模块内部定义的语法,我更加推荐采用 Verilog-2001 中在模块接口声明中定义的语法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module module_name
#(
parameter parameter_name = parameter_default_value
) (
...
)

...
endmodule

module_name #(
.parameter_name(parameter_value)
) (
...
);

localparam 是模块内部定义的参数,语法如 localparam localparam_name = localparam_value

`define 是 Verilog 的宏定义,与 C 宏的文本替换相似。宏除了用于定义常量,还可以用来简化代码的编写,例如:

1
2
`define packed_wires = {wire_1, wire_2, wire_3}
packed_wires = 3'b101

变基部分选择(Indexed part-select)

可以使用 wire_name[index_wire_name] 的方式来实现一位宽度的多路选择器。相应地,Verilog-2001 也提供了 wire_name[WIDTH * index_wire_name +: WIDTH] 的方式来实现多位宽度的多路选择器。详情可以参考这个 StackOverflow 问题:

What is this operator called as “+:” in verilog – Electrical Engineering Stack Exchange

然而这个语法的综合有一些怪异的地方,有时会导致综合成移位器而非多路选择器,消耗较多的资源,使用时需要留意一下综合报告。

对表达式进行选择

在 Verilog 中,无法直接对 wire_name + 1'b1 这样的表达式选择某些位,但可以其实通过加上花括号的方式进行选择,例如 {wire_name + 1'b1}[3:0]。这个形式可以用于显式地截短运算结果并且不触发警告。

然而这个 trick 对于变基部分选择无效。以及似乎在某些旧型号的硬件上 XST 无法识别这个语法。

代码简化

可以采用 generatetaskfunction 简化代码逻辑的编写,详细的使用方法在 Verilog General Guide 中已经说明,故不再赘述。

信号宽度警告

信号宽度警告是一种十分有用的警告,因为许多低级错误都是由于错误地(或忘记)指定信号宽度导致的。请务必仔细检查综合报告。

由于裸写的非零十进制整数字面量默认为 32 位,容易增加多余的警告,因此建议在书写字面量时总是使用 2'b10'd16'h 这样的前缀形式。

至于对信号进行递增并且在溢出后自动归零,可以采用 reg_name = reg_name + 1'b1 的形式,综合器不会将此判断为溢出而发出警告。

组合逻辑

在 Verilog 中组合逻辑可以通过在 always @* 块中使用 ifswitch 和阻塞赋值 = 实现,也可以直接使用 assign?: 这个条件运算符实现。

我个人的建议是避免使用 always 块实现组合逻辑,因为在用 ifswitch 实现逻辑时,很容易忘记书写某些情况下的默认值,导致综合结果为 FF/Latch 的时序电路而非组合电路,并且这件事情很难在综合报告中发现。

我目前采取的实践是仅将 always 块用于实现时序电路,而使用条件运算符实现组合逻辑。

顺带提及,always @* 用于实现组合电路,应该只使用阻塞赋值 =always @(posedge clock) 用于实现时序电路,应该只使用非阻塞赋值 <=;两者混用依然可以成功综合,但是意义不明,十分容易出错。

Lint

对于长时间调试难以找出的错误,可以尝试使用 Lint 工具对代码进行静态检查,它比 XST 综合器的检查更加严格,也常常能指出代码中埋藏的许多低级错误(我曾经用它在十分钟内找出了一个调试了一整天未能找出的 Bug)。

Verilator 是一个免费的 Verilog 模拟器,其中也包含了 Lint 功能。安装 verilator后,执行 verilator --lint-only top.v 即可开始检查。

其他

综合过程中输出的 Simulation mismatch 警告不能无视,否则可能会导致不稳定的综合结果和奇怪的错误。

结语

除了某些语法检查不够严格,Verilog 其实是一门设计得较为直觉的语言,语法结构大多可以映射到电路实现,有着 C 一般的简洁和直观。如果遵循一定的编码规范和最佳实践,使用硬件而非软件的思维进行编码,还是可以较为简单地达成目标的。

前言

本文章主要面向的是已经基本熟悉 C 语言的初学者,而目的则在于通过对 C 语言具体机制的介绍,使得读者可以理解其本质,面对问题时,能够通过语言的 设计思想 而非 强制记忆的规则 得出正确的答案。

所采取的方式是,通过对某个语言机制 存在的原因 ,来理解这个特性 为何这样设计 ,并得出一些 基本的原则 ,以至于 可以推测 在其他情景下这个特性会如何表现。适当的时候,会结合一些例子说明问题。

给楚楚。

静态

这一部分主要介绍 C 语言中的静态部分,即语法相关。

在开始之前,有一个基本原则可以记住:

基本原则

C 语言是一门直接面向内存操作的语言。

C 语言在本质上不过是在按规则不断读写内存而已。这一点在之后会不断体现。

数据类型

C 中常见的数据类型有 intlongfloatdouble 等等基础类型,和 structunionenum 等自定义类型。

数据类型的存在,是为了给内存里本身并 没有意义 的二进制数据,提供一个 理解这些数据的方式。因此,int 类型会导致 C 语言认为这个位置上的二进制们是一个特定长度的整数,并按照整数的加减乘除进行运算;而 float 类型会导致 C 语言把这些数据理解成一个浮点数来处理。

总的来说,内存里的数据本身没有意义,有了数据类型规定的理解方式后,它们才有了意义。

但是,另外需要注意的一点是,数据类型的存在,只是为了告诉 C 语言的编译器如何处理数据,由此来生成 CPU 指令。而在 编译之后 实际运行时,只有 CPU 对内存作数学运算,并 不会留有任何关于数据类型的信息,这也是一条重要的原则。

重要原则

C 语言编译后数据类型就不再存在,即数据类型只用于编译时帮助生成代码。

指针

关于指针最重要的一点:

重要原则

指针在本质上只是一个整数。

这一点请时刻牢记。

因此,指针存在的作用是,为了能够引用内存中任意位置的数据,需要将它的地址这个整数,保存在某种的类型变量里。这种类型就是指针类型,这种类型的 内容就是一个整数 ,不过是这个整数被 理解为内存地址 而已。

指针特有的操作是 解引用 。解引用的操作,就是把指针变量所存储的那个整数取出,作为内存地址理解,然后把对这个变量的取值或者赋值, 转化为对那个内存地址上内容的取值或赋值

由于指针的值不过是一个整数,因此可以像整数一样进行加减来计算地址,称为 指针运算 。与普通的整数运算不同,指针每次加 1,都是将指针所存储的地址的值,加上指针 所指向的那个类型占据的大小 ,这样新的地址值就会 指向下一个 这个类型的数据。即如下例:

1
2
long b[4] = {0}, *a = b;
a += 3; // a 存储的地址将增加 3 * sizeof(long),即指向 b[3]。

结构体

结构体的存在,是因为程序员表达一个事物可能需要多个基础数据类型的量,但将一个个量在函数等之间 单独传递过于麻烦 ,所以提供一种机制把多个量 打包一起处理

重要原则

结构体的本质是一个偏移量表(以及由此知道的总长度)。

这一点会在不同的场景下不断体现。

可以通过 .-> 访问结构体的成员 。在访问成员时,实际上,只是取得结构体在内存里的位置, 加上这个成员相对于结构体开始的偏移量 ,来 访问这个新位置上内存中的内容 而已。

// TODO: &(NULL->a)

类型转换

类型转换分为两种,一种是基础数据类型间的转换,一种是指针类型的转换。

基础数据类型有 intlongfloatdouble 等,在它们之间进行相互转换时,是将数据 按照原有类型理解 以后,重新 以另一种类型规定的方式把这个值存储 到另一个地方。

例如,在将 int 转换为 float 时,int直接采用补码表示一个整数,类型转换时按照补码理解这个数的值,然后通过运算,计算出 float 需要的 IEEE 754 格式的值(符号位、指数、尾数)给使用者。二者在内存中的表示其实完全不同,是编译器会生成代码帮助程序员完成这个转换。

重要原则

指针类型间的转换可以理解为只是为了 C 语言的类型检查,编译时不会产生实际代码。

也就是说,编译器需要知道指针所指向数据的类型,才能知道应该 怎样操作 指向的这块数据,以及 检查 出不合法的操作。类型转换,只是程序员明确告诉编译器指向的这块数据可以被 重新理解 为另一种类型而已,然后编译器就会按照这种类型操作。但实际上,这种重新理解只需要在编译的时候知道即可,所以编译后不会有相关的代码。

// TODO:结构体间类型转换。

实际情况下,不同指针类型的长度可能不同,所以有时会发生实际的扩展或压缩地址长度的操作,这一点知道即可。

指针与数组

// TODO: 正在写作。

函数调用

// TOOD: 正在写作。

前言

这篇文章是我在操作系统原理课程的作业。作业选题本身很宽,大意是只要描述操作系统的发展即可。因为早就对 Plan 9 这个旨在取代 Unix 的操作系统有兴趣,又可以借此花时间仔细理解和实际使用一次这个系统,于是毫不犹豫地选择了这个题目。

以下就是我自己对 Plan 9 这个操作系统在设计上的理解和概括。

简介

Plan 9 是一款分布式操作系统,由贝尔实验室计算机科学研究中心在 19 世纪 80 年代中期开始开发,旨在成为 Unix 的后继者。Plan 9 的团队正是曾开发 Unix 和 C 语言的团队,开发过程中参与者包括 Ken Thompson、Dennis Ritchie、Bjarne Stroustrup 等人。

本文将主要介绍 Plan 9 的部分设计理念。

设计

文件

Plan 9 继承了 Unix 中“ 任何事物都是文件”的哲学,并且对其进一步扩展,将所有计算资源都视为文件进行管理,使用读取和写入操作作为与资源交互的统一方式。

例如,在 Unix 中对许多具体硬件控制需要使用 ioctl 系统调用进行,以及 X Window 等系统中对于资源也使用函数调用控制而非用文件代表,但在 Plan 9 中,无论是 CPU、外围设备、网络,还是图形界面本身,设计者始终采用文件来代表资源并与之交互。

在这个意义下,其实文件的意义并非传统的磁盘存储的单元,而是一个指代一般意义上计算资源的名字。

文件系统

Plan 9 与 Unix 同样采用的是层次性的文件系统。由于文件实际上就是资源,所以文件的路径实际上也与 URI 的意义类似,即计算资源可以通过特定的路径访问。

在文件的组织方式上,Plan 9 使用了与 Unix 类似约定的命名方式,例如也可以使用 ls /proc 查看所有进程等。

Plan 9 的文件系统并非传统意义上局限于磁盘的文件系统。在 Plan 9 中,由于资源即是文件,资源本身来自本地设备还是需要通过网络访问其实只是实现细节,所以两者在文件系统中具有统一的表示。Plan 9 采用一种名为 9P 的协议对资源的访问过程进行封装。经过这种抽象,系统中对远端和本机资源进行访问的接口达成了一致,由此通过分布式的文件系统从系统设计上实现了分布式计算的基础,例如即使是 CPU 资源也可以通过文件方便地共享。

命名空间

文件系统只是资源的组织形式,而允许不同程序对资源采取不同的组织形式可以带来很大的可扩展性,因此 Plan 9 对每个进程使用使用了不同的文件系统,称为命名空间,并由此实现了资源的进程隔离。

此外,父进程还可以以 9P 协议向子进程的命名空间提供虚拟文件(以文件作为服务),这样实现了一种低成本而原生的跨进程资源访问,也使得提供给子进程资源可以被自由地替换。由此,实现 VPN 连接只需要将 /net 目录代理,实现窗口系统只需要将 bitblt 文件代理,等等。

合并目录

因为要替换子进程文件系统中的目录,但目录中的内容又并非全部都需要重新提供,合并目录就成为了一个良好的解决方案。

Plan 9 中的合并目录是一种类似 Unix 中挂载和搜索路径相结合的做法。通过将目录甲合并至目录乙,访问目录乙时将会先在目录甲中进行查找,未找到时再在目录乙本身中查询。将这个设计与网络结合,则可以产生将远端的 /bin 目录合并至本地即可直接使用远端程序这样的使用方法。

UTF-8

Plan 9 更加为人知晓的一个组件则是由 Ken Thompson 提出的 UTF-8 编码。通过这种编码方式,Unicode 自动兼容于原先的 ASCII 字符,不会出现需要编码转换的问题,因此时至今日已经被广泛采用。而 UTF-8 本身则早已是 Plan 9 的原生编码。

发展

虽然 Plan 9 有着相对于 Unix 更加普适和可扩展的设计,但在实际使用中它并没有赢得太多的用户。

Plan 9 在 1992 年向大学公开,并在 1995 年由 AT&T 商业发布。然而 1996 年,AT&T 已将重心转移至 Inferno,一个基于 Plan 9 思想设计并且旨在与 Java 竞争的系统。到了 2000 年,掌管贝尔实验室的朗讯决定停止 Plan 9 的商业支持,并在几年之后将 Plan 9 的代码以自由软件许可的形式向大众公开。

评价

Plan 9 对 Unix 中的许多理念做了进一步的提升和扩展,对资源管理和分布式计算进行了优秀而统一的实现,在操作系统架构的历史上具有不可磨灭的意义;来自其中的 UTF-8、rc shell 等组件,也被其他操作系统所吸纳接受;并且,Plan 9 的后继者 Inferno 和 Plan B 还在继续发展。

但是,仅有优雅的设计,却缺乏相应的生态,这导致了 Plan 9 在实际应用中的结果不成功,令人惋惜。这一切正如 Eric Raymond 所说,足以让目标高远的软件工程师们时时警醒:

Plan 9 会失败,纯粹只是因为它的改进程度没有大到能取代 Unix。与 Plan 9 相比,Unix 虽然破破烂烂带有明显的缺陷,但还是能够把工作良好地完成,而这就足以保住它的地位了。

这件事情教给了那些怀有雄心壮志的系统架构师一个道理:一个更优解决方案所面临的最危险的敌人,其实是那些能把事情刚好完成的程序。

致谢

本文写作过程中参考了 Plan 9 from Bell Labs – Wikipedia, the free encyclopedia贝尔实验室九号计划 – 维基百科,自由的百科全书 等页面的内容,在此表示感谢。