第6章: Unicode、並行システム、信頼性プロトコル
6.1 文字コードの歴史とUnicodeの誕生
6.1.1 バベルの塔：文字コードの分裂
1960年代から1980年代にかけて、コンピュータ業界は深刻な問題に直面していた。各国、各ベンダーが独自の文字コードを開発し、相互運用性が失われていった。
文字コードの乱立
時系列：文字コードの分裂
1963年 - ASCII (7ビット、128文字)
1967年 - EBCDIC (IBM メインフレーム用)
1969年 - JIS X 0201 (日本のカタカナ)
1978年 - JIS X 0208 (日本語漢字)
1981年 - Shift_JIS (Microsoft/IBM PC)
1984年 - EUC-JP (UNIX用日本語)
1985年 - ISO 8859-1 (西欧言語)
1987年 - GB 2312 (中国語簡体字)
1990年 - Big5 (中国語繁体字)
1991年 - Unicode 1.0 (統一規格)
この状況は「文字コードのバベルの塔」と呼ばれた。同じ文字列が異なるシステムでは文字化けを起こし、国際的なデータ交換は困難を極めた。
6.1.2 Unicode Consortiumの設立（1991年）
1987年、XeroxのJoe BeckerとAppleのLee Collinsは、すべての言語を統一的に表現できる文字コードの開発を提案した。
Unicodeの設計原則
> "Unicode provides a unique number for every character, no matter what the platform, no matter what the program, no matter what the language." > > — Unicode Consortium, 1991
Unicodeの基本概念
| 用語 | 説明 | 例 | |------|------|-----| | コードポイント | 文字に割り当てられた数値 | U+0041 = 'A' | | コードスペース | 0x0000〜0x10FFFF | 約111万点 | | BMP | Basic Multilingual Plane (U+0000〜U+FFFF) | 一般的な文字 | | サロゲートペア | BMPを超える文字の表現 | 絵文字など |
Unicodeの構造：
プレーン0（BMP）: U+0000 - U+FFFF
├── U+0000 - U+007F : ASCII互換（基本ラテン文字）
├── U+0080 - U+00FF : ラテン補助
├── U+0100 - U+017F : ラテン拡張A
├── U+3040 - U+309F : ひらがな
├── U+30A0 - U+30FF : カタカナ
└── U+4E00 - U+9FFF : CJK統合漢字
プレーン1: U+10000 - U+1FFFF
└── U+1F600 - U+1F64F : 絵文字
プレーン2: U+20000 - U+2FFFF
└── CJK統合漢字拡張B
6.1.3 UTF-8の発明（1992年）
1992年9月、Ken ThompsonとRob Pikeは、Plan 9オペレーティングシステムのために新しいエンコーディング形式を考案した。これがUTF-8である。
UTF-8の設計原則
Thompson とPikeの設計目標：
- ASCII後方互換性：既存のASCIIテキストは変更なしで有効なUTF-8
- 自己同期性：任意のバイトから文字境界を特定可能
- バイト順非依存：エンディアンの問題が発生しない
- NUL終端互換：C言語の文字列関数と互換
UTF-8のエンコーディング規則
ビット数 バイト数 形式
7 1 0xxxxxxx
11 2 110xxxxx 10xxxxxx
16 3 1110xxxx 10xxxxxx 10xxxxxx
21 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
例：
'A' (U+0041) → 0x41 (1バイト)
'あ' (U+3042) → 0xE3 0x81 0x82 (3バイト)
'😀' (U+1F600) → 0xF0 0x9F 0x98 0x80 (4バイト)
UTF-8の自己同期性
バイトパターン：
0xxxxxxx : ASCIIまたは1バイト文字の開始
10xxxxxx : 継続バイト（文字の途中）
11xxxxxx : マルチバイト文字の開始
例：文字列 "あA" のバイト列
E3 81 82 41
↓ ↓ ↓ ↓
開始 継続 継続 開始（ASCII）
任意の位置から開始しても、
- 10xxxで始まるバイトは継続バイト→前に戻る
- それ以外は文字の開始
6.1.4 UTF-8の数学的解析
符号化効率の分析
Claude Shannonの情報理論（1948年）に基づき、UTF-8の効率を分析する：
英語テキストの場合：
- ASCII文字のみ → 1バイト/文字
- 圧縮率 = 1.0（圧縮なし）
日本語テキストの場合：
- ひらがな/カタカナ/漢字 → 3バイト/文字
- UTF-16では2バイト/文字
- UTF-8/UTF-16比 = 1.5
混合テキストの場合：
- ASCII + 日本語が混在
- Webページの平均：UTF-8が最も効率的
6.2 並行システムの理論
6.2.1 並行性の理論的基礎
Edsger Dijkstraのセマフォ（1965年）
1965年、Dijkstraは並行プログラミングの基本的な同期機構であるセマフォを提案した。
// Dijkstraのセマフォ（擬似コード）
typedef struct {
int value;
queue waiting_processes;
} semaphore;
void P(semaphore *s) { // Wait / Proberen
if (s->value > 0) {
s->value--;
} else {
// プロセスをキューに追加してブロック
block(current_process);
}
}
void V(semaphore *s) { // Signal / Verhogen
if (waiting_processes_exist(s)) {
// 待機中のプロセスを起床
wakeup(dequeue(s->waiting_processes));
} else {
s->value++;
}
}
C.A.R. Hoareのモニタ（1974年）
1974年、Tony Hoareはセマフォを抽象化したモニタの概念を提案した：
モニタの特性：
1. 相互排除：同時に1つのスレッドのみがモニタ内で実行
2. 条件変数：待機と通知のメカニズム
3. カプセル化：データとその操作を一体化
6.2.2 レースコンディションと臨界区間
レースコンディションの形式的定義
定義（レースコンディション）
レースコンディションは、2つ以上の実行スレッドが
共有リソースに同時アクセスし、少なくとも1つが
書き込みを行うときに発生する非決定的動作。
条件：
1. 共有状態が存在する
2. 複数のスレッドがアクセスする
3. 少なくとも1つの書き込み操作がある
4. 適切な同期がない
Minitalkにおけるレースコンディション
// 危険なコード例
static int bit_count = 0; // 共有状態
static unsigned char current_char = 0;
void signal_handler(int signum) {
current_char <<= 1; // 読み取り-修正-書き込み
if (signum == SIGUSR2)
current_char |= 1;
bit_count++; // 読み取り-インクリメント-書き込み
// 問題：ハンドラ実行中に新しいシグナルが来ると
// bit_countやcurrent_charが不整合になる可能性
}
// 解決策：シグナルマスクで保護
void safe_handler(int signum, siginfo_t *info, void *ctx) {
// シグナルマスクにより、このハンドラ実行中は
// SIGUSR1/SIGUSR2がブロックされる
// → レースコンディションを防止
}
6.2.3 マルチクライアントの理論
並行サーバーモデル
モデル1：シングルスレッド・マルチプレクシング
┌─────────────────────────────────────┐
│ サーバー │
│ ┌─────────────────────────────┐ │
│ │ イベントループ │ │
│ │ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ │
│ │ │C1 │ │C2 │ │C3 │ │C4 │ │ │
│ │ └───┘ └───┘ └───┘ └───┘ │ │
│ └─────────────────────────────┘ │
└─────────────────────────────────────┘
Minitalkの場合：
- シングルプロセス・シングルスレッド
- シグナルをイベントとして処理
- クライアント状態を配列で管理
クライアント管理の形式化
定義（マルチクライアント状態）
M = (C, S, T) where:
C = {c₁, c₂, ..., cₙ} : クライアント集合（最大N）
S : C → State : 状態関数
T : C → Timestamp : 最終アクティビティ時刻
State = (pid, current_char, bit_count, active)
不変条件：
1. |{c ∈ C | active(c)}| ≤ MAX_CLIENTS
2. ∀c ∈ C: bit_count(c) ∈ [0, 7]
3. ∀c₁, c₂ ∈ C: c₁ ≠ c₂ → pid(c₁) ≠ pid(c₂)
6.3 信頼性プロトコルの設計
6.3.1 停止待機プロトコル（Stop-and-Wait）
ARQ（Automatic Repeat Request）の歴史
1960年代のデータ通信で、エラー訂正のためにARQプロトコルが開発された。
停止待機プロトコルの形式化
プロトコル仕様：
送信者：
1. フレームを送信
2. ACKを待機（タイムアウト付き）
3. ACK受信 → 次のフレームへ
タイムアウト → フレームを再送
受信者：
1. フレームを受信
2. 検証 → ACKを送信
エラー → NAKまたは無視
Minitalkでの実装：
- フレーム = 1ビット（シグナル）
- ACK = SIGUSR1
- タイムアウト = ACK_TIMEOUT μs
スループット分析
停止待機プロトコルのスループット：
U = T_frame / (T_frame + 2 × T_prop + T_ack)
where:
T_frame : フレーム送信時間
T_prop : 伝搬遅延
T_ack : ACK送信時間
Minitalkの場合（概算）：
T_signal ≈ 1μs（シグナル送信）
T_context ≈ 10-100μs（コンテキストスイッチ）
T_ack ≈ 1μs
実効スループット ≈ 100-1000 bits/sec
6.3.2 ウィンドウプロトコル（発展的話題）
スライディングウィンドウ
より高いスループットを実現するために、複数のフレームを同時に送信するスライディングウィンドウプロトコルがある：
Go-Back-N (GBN)：
- ウィンドウサイズW
- W個のフレームを確認なしで送信可能
- エラー時はウィンドウ内のすべてを再送
Selective Repeat (SR)：
- エラーのあったフレームのみ再送
- 受信側にバッファが必要
Minitalkでは実装が複雑すぎるため、
停止待機プロトコルが適切
6.4 データ圧縮の理論
6.4.1 情報理論と圧縮限界
Shannonの情報源符号化定理（1948年）
Claude Shannonは、データ圧縮の理論的限界を証明した：
> "A message can be compressed to an average length no shorter than its entropy, and this bound can be approached arbitrarily closely." > > — Claude Shannon, "A Mathematical Theory of Communication", 1948
エントロピーの定義
定義（情報エントロピー）
H(X) = -Σ p(xᵢ) log₂ p(xᵢ)
where:
X : 確率変数（情報源）
p(xᵢ) : 記号xᵢの出現確率
例：公平なコイン
p(heads) = p(tails) = 0.5
H = -0.5 log₂(0.5) - 0.5 log₂(0.5) = 1 bit
例：偏ったコイン
p(heads) = 0.9, p(tails) = 0.1
H = -0.9 log₂(0.9) - 0.1 log₂(0.1) ≈ 0.47 bits
6.4.2 ランレングス符号化（RLE）
David Huffman以前の単純な圧縮
ランレングス符号化は、連続する同一文字を「文字×回数」で表現する：
例：
入力： "AAAAAABBBCC"
出力： "6A3B2C"
形式：
count (1 byte) + value (1 byte)
利点：連続データに効果的
欠点：ランダムデータでは膨張
RLEの形式的定義
定義（RLEエンコード）
encode : Σ* → (N × Σ)*
encode(s) = [(n₁, c₁), (n₂, c₂), ..., (nₖ, cₖ)]
where:
s = c₁^n₁ c₂^n₂ ... cₖ^nₖ
cᵢ ≠ cᵢ₊₁ for all i
6.4.3 Huffman符号化（1952年）
David Huffmanの発明
1952年、MIT大学院生だったDavid Huffmanは、情報理論の授業の課題として最適な可変長符号を考案した。
Huffman符号の構築アルゴリズム：
1. 各記号とその頻度でノードを作成
2. 最小頻度の2ノードを選択
3. 新ノードを作成（頻度 = 2ノードの和）
4. 2つのノードを新ノードの子とする
5. ノードが1つになるまで繰り返す
6. 左の枝を0、右の枝を1とする
例：
記号 頻度 Huffman符号
A 5 0
B 2 100
C 2 101
D 1 110
E 1 111
6.5 暗号学の基礎
6.5.1 古典暗号の歴史
シーザー暗号（紀元前1世紀）
Julius Caesarが使用したとされる、最古の暗号の一つ：
シーザー暗号の数学的定義：
E(x) = (x + k) mod 26 （暗号化）
D(x) = (x - k) mod 26 （復号）
where:
x : 平文の文字位置（A=0, B=1, ..., Z=25）
k : シフト量（鍵）
例（k=3）：
平文: HELLO
暗号文: KHOOR
Kerckhoffsの原則（1883年）
オランダの暗号学者Auguste Kerckhoffsは、暗号システムの設計原則を提唱した：
> "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge." > > — Auguste Kerckhoffs, 1883
この原則は現代暗号学の基礎となっている。
6.5.2 排他的論理和（XOR）暗号
XOR暗号の数学的性質
XORの性質：
1. A ⊕ 0 = A （恒等元）
2. A ⊕ A = 0 （逆元）
3. A ⊕ B = B ⊕ A （交換律）
4. (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) （結合律）
暗号化と復号：
C = P ⊕ K （暗号化）
P = C ⊕ K （復号）
証明：
C ⊕ K = (P ⊕ K) ⊕ K = P ⊕ (K ⊕ K) = P ⊕ 0 = P
ワンタイムパッド（1917年）
Gilbert Vernamが発明した、情報理論的に安全な唯一の暗号：
条件：
1. 鍵は平文と同じ長さ
2. 鍵は真にランダム
3. 鍵は一度だけ使用
これを満たすとき、XOR暗号は
理論的に解読不可能（Shannonが証明、1949年）
6.6 Minitalkボーナス機能の実装
6.6.1 UTF-8サポートの実装
/* UTF-8文字長の判定
* 先頭バイトのビットパターンで判定
*/
int utf8_char_len(unsigned char first_byte)
{
/* ASCII：0xxxxxxx */
if ((first_byte & 0x80) == 0x00)
return (1);
/* 2バイト：110xxxxx */
if ((first_byte & 0xE0) == 0xC0)
return (2);
/* 3バイト：1110xxxx */
if ((first_byte & 0xF0) == 0xE0)
return (3);
/* 4バイト：11110xxx */
if ((first_byte & 0xF8) == 0xF0)
return (4);
return (-1); /* 無効なUTF-8 */
}
/* 継続バイトの検証
* 継続バイトは10xxxxxxの形式
*/
int is_utf8_continuation(unsigned char byte)
{
return ((byte & 0xC0) == 0x80);
}
/* UTF-8シーケンスの妥当性検証 */
int validate_utf8(const unsigned char *str, int len)
{
int i;
int char_len;
int j;
i = 0;
while (i < len && str[i])
{
char_len = utf8_char_len(str[i]);
if (char_len == -1)
return (0);
/* 継続バイトを検証 */
j = 1;
while (j < char_len)
{
if (i + j >= len || !is_utf8_continuation(str[i + j]))
return (0);
j++;
}
/* オーバーロング符号化の検出 */
if (char_len == 2 && (str[i] & 0x1E) == 0)
return (0);
if (char_len == 3 && str[i] == 0xE0 && (str[i+1] & 0x20) == 0)
return (0);
i += char_len;
}
return (1);
}
/* UTF-8文字列の送信 */
int send_utf8_string(pid_t server_pid, const char *str)
{
int i;
int char_len;
/* まずUTF-8の妥当性を検証 */
if (!validate_utf8((unsigned char *)str, ft_strlen(str)))
{
write(2, "Error: Invalid UTF-8 sequence\n", 30);
return (0);
}
i = 0;
while (str[i])
{
char_len = utf8_char_len((unsigned char)str[i]);
/* 文字の全バイトを送信 */
while (char_len > 0)
{
if (!send_char(server_pid, str[i]))
return (0);
i++;
char_len--;
}
}
/* NULL終端を送信 */
return (send_char(server_pid, '\0'));
}
6.6.2 マルチクライアント対応
#define MAX_CLIENTS 10
#define CLIENT_TIMEOUT 60
/* クライアント情報構造体 */
typedef struct s_client_info
{
pid_t pid; /* クライアントPID */
unsigned char current_char; /* 受信中の文字 */
int bit_count; /* 受信ビット数 */
time_t last_activity; /* 最終アクティビティ */
int active; /* アクティブフラグ */
} t_client_info;
/* サーバー状態構造体 */
typedef struct s_server
{
t_client_info clients[MAX_CLIENTS];
int client_count;
} t_server;
static t_server g_server = {{0}, 0};
/* クライアント検索：O(n)線形探索 */
int find_client(pid_t pid)
{
int i;
for (i = 0; i < MAX_CLIENTS; i++)
{
if (g_server.clients[i].active &&
g_server.clients[i].pid == pid)
return (i);
}
return (-1);
}
/* クライアント追加：最初の空きスロットを使用 */
int add_client(pid_t pid)
{
int i;
for (i = 0; i < MAX_CLIENTS; i++)
{
if (!g_server.clients[i].active)
{
g_server.clients[i].pid = pid;
g_server.clients[i].current_char = 0;
g_server.clients[i].bit_count = 0;
g_server.clients[i].last_activity = time(NULL);
g_server.clients[i].active = 1;
g_server.client_count++;
return (i);
}
}
return (-1); /* 満杯 */
}
/* クライアント削除 */
void remove_client(int index)
{
if (index >= 0 && index < MAX_CLIENTS &&
g_server.clients[index].active)
{
g_server.clients[index].active = 0;
g_server.clients[index].pid = 0;
g_server.client_count--;
}
}
/* マルチクライアント対応シグナルハンドラ */
void multi_client_handler(int signum, siginfo_t *info, void *context)
{
int client_idx;
t_client_info *client;
(void)context;
/* クライアントを検索または追加 */
client_idx = find_client(info->si_pid);
if (client_idx == -1)
{
client_idx = add_client(info->si_pid);
if (client_idx == -1)
{
write(2, "Error: Too many clients\n", 24);
kill(info->si_pid, SIGUSR2); /* 拒否を通知 */
return ;
}
write(1, "\n[New client: ", 14);
ft_putnbr(info->si_pid);
write(1, "]\n", 2);
}
client = &g_server.clients[client_idx];
client->last_activity = time(NULL);
/* ビット処理（通常のハンドラと同じ）*/
client->current_char <<= 1;
if (signum == SIGUSR2)
client->current_char |= 1;
client->bit_count++;
if (client->bit_count == 8)
{
if (client->current_char == '\0')
{
write(1, "\n[Client ", 9);
ft_putnbr(client->pid);
write(1, " disconnected]\n", 15);
kill(client->pid, SIGUSR2); /* 終了ACK */
remove_client(client_idx);
}
else
{
write(1, &client->current_char, 1);
kill(client->pid, SIGUSR1); /* ACK */
}
client->current_char = 0;
client->bit_count = 0;
}
}
/* 非アクティブクライアントのクリーンアップ */
void cleanup_inactive_clients(void)
{
time_t now;
int i;
now = time(NULL);
for (i = 0; i < MAX_CLIENTS; i++)
{
if (g_server.clients[i].active &&
now - g_server.clients[i].last_activity > CLIENT_TIMEOUT)
{
write(2, "Timeout: removing client ", 25);
ft_putnbr(g_server.clients[i].pid);
write(2, "\n", 1);
remove_client(i);
}
}
}
6.6.3 確認応答機構（ACK）の強化
/* 拡張ACK機構
* ビット単位ではなく文字単位でACK
*/
/* クライアント側：強化された送信 */
typedef struct s_enhanced_client
{
volatile sig_atomic_t ack_received;
volatile sig_atomic_t ack_type; /* SIGUSR1=char ACK, SIGUSR2=done */
int retry_count;
int adaptive_delay;
} t_enhanced_client;
static t_enhanced_client g_eclient = {0, 0, 0, 100};
void enhanced_ack_handler(int signum)
{
g_eclient.ack_received = 1;
g_eclient.ack_type = signum;
}
/* 文字送信（8ビット一括、文字レベルACK）*/
int send_char_enhanced(pid_t server_pid, unsigned char c)
{
int bit;
int retry;
int timeout;
for (retry = 0; retry < MAX_RETRY; retry++)
{
g_eclient.ack_received = 0;
/* 8ビット送信 */
for (bit = 7; bit >= 0; bit--)
{
if (kill(server_pid, ((c >> bit) & 1) ? SIGUSR2 : SIGUSR1) == -1)
return (0);
usleep(g_eclient.adaptive_delay);
}
/* 文字レベルACKを待機 */
timeout = ACK_TIMEOUT * 8; /* 文字全体のタイムアウト */
while (!g_eclient.ack_received && timeout > 0)
{
usleep(10);
timeout -= 10;
}
if (g_eclient.ack_received)
{
/* 成功時は遅延を減少 */
if (g_eclient.adaptive_delay > 50)
g_eclient.adaptive_delay--;
return (1);
}
/* 失敗時は遅延を増加 */
g_eclient.adaptive_delay += 20;
write(2, "Retrying character...\n", 22);
}
return (0);
}
6.7 バイナリファイル転送
6.7.1 ファイル転送プロトコル
/* ファイル転送プロトコルのヘッダー */
typedef struct s_file_header
{
unsigned char magic[4]; /* "MTFP" (Minitalk File Protocol) */
unsigned int file_size; /* ファイルサイズ（4バイト）*/
unsigned char checksum; /* 簡易チェックサム */
} t_file_header;
/* チェックサム計算（簡易版）*/
unsigned char calculate_checksum(const unsigned char *data, int size)
{
unsigned char sum;
int i;
sum = 0;
for (i = 0; i < size; i++)
sum ^= data[i];
return (sum);
}
/* ファイル読み込み */
unsigned char *read_file(const char *filename, int *size)
{
int fd;
unsigned char *buffer;
int bytes_read;
fd = open(filename, O_RDONLY);
if (fd == -1)
return (NULL);
/* ファイルサイズ取得 */
*size = lseek(fd, 0, SEEK_END);
lseek(fd, 0, SEEK_SET);
buffer = malloc(*size);
if (!buffer)
{
close(fd);
return (NULL);
}
bytes_read = read(fd, buffer, *size);
close(fd);
if (bytes_read != *size)
{
free(buffer);
return (NULL);
}
return (buffer);
}
/* ファイル送信 */
int send_file(pid_t server_pid, const char *filename)
{
unsigned char *data;
t_file_header header;
int size;
int i;
data = read_file(filename, &size);
if (!data)
return (0);
/* ヘッダー構築 */
header.magic[0] = 'M';
header.magic[1] = 'T';
header.magic[2] = 'F';
header.magic[3] = 'P';
header.file_size = size;
header.checksum = calculate_checksum(data, size);
/* ヘッダー送信 */
for (i = 0; i < 4; i++)
send_char(server_pid, header.magic[i]);
send_char(server_pid, (size >> 24) & 0xFF);
send_char(server_pid, (size >> 16) & 0xFF);
send_char(server_pid, (size >> 8) & 0xFF);
send_char(server_pid, size & 0xFF);
send_char(server_pid, header.checksum);
/* データ送信（プログレス表示付き）*/
for (i = 0; i < size; i++)
{
if (!send_char(server_pid, data[i]))
{
free(data);
return (0);
}
if (i % 100 == 0)
print_progress(i, size);
}
print_progress(size, size);
write(1, "\n", 1);
free(data);
return (1);
}
6.8 データ圧縮の実装
6.8.1 RLE圧縮
/* RLE圧縮の実装 */
typedef struct s_rle_result
{
unsigned char *data;
int size;
} t_rle_result;
t_rle_result *compress_rle(const unsigned char *input, int input_size)
{
t_rle_result *result;
unsigned char *compressed;
int i;
int j;
int count;
/* 最悪ケースでは2倍のサイズ */
compressed = malloc(input_size * 2);
if (!compressed)
return (NULL);
i = 0;
j = 0;
while (i < input_size)
{
count = 1;
/* 連続する同一バイトをカウント */
while (i + count < input_size &&
input[i] == input[i + count] &&
count < 255)
count++;
compressed[j++] = count;
compressed[j++] = input[i];
i += count;
}
result = malloc(sizeof(t_rle_result));
if (!result)
{
free(compressed);
return (NULL);
}
result->data = compressed;
result->size = j;
return (result);
}
/* RLE解凍 */
unsigned char *decompress_rle(const unsigned char *compressed,
int compressed_size, int *output_size)
{
unsigned char *output;
int i;
int j;
int count;
int k;
/* 最大展開サイズを計算 */
output = malloc(compressed_size / 2 * 255);
if (!output)
return (NULL);
i = 0;
j = 0;
while (i < compressed_size)
{
count = compressed[i++];
for (k = 0; k < count; k++)
output[j++] = compressed[i];
i++;
}
*output_size = j;
return (output);
}
/* 圧縮送信 */
int send_compressed(pid_t server_pid, const char *str)
{
t_rle_result *compressed;
int original_size;
double ratio;
original_size = ft_strlen(str);
compressed = compress_rle((unsigned char *)str, original_size);
if (!compressed)
return (0);
ratio = (double)compressed->size / original_size;
write(1, "Compression ratio: ", 19);
ft_putnbr((int)(ratio * 100));
write(1, "%\n", 2);
/* 圧縮マーカーと元サイズを送信 */
send_char(server_pid, 0xFF); /* 圧縮フラグ */
send_char(server_pid, (original_size >> 8) & 0xFF);
send_char(server_pid, original_size & 0xFF);
/* 圧縮データを送信 */
for (int i = 0; i < compressed->size; i++)
{
if (!send_char(server_pid, compressed->data[i]))
{
free(compressed->data);
free(compressed);
return (0);
}
}
free(compressed->data);
free(compressed);
return (1);
}
6.9 暗号化の実装
6.9.1 XOR暗号
/* XOR暗号化（Vernam暗号の簡易版）*/
void xor_cipher(unsigned char *data, int size, const char *key)
{
int key_len;
int i;
key_len = ft_strlen(key);
for (i = 0; i < size; i++)
data[i] ^= key[i % key_len];
}
/* 暗号化送信 */
int send_encrypted(pid_t server_pid, const char *str, const char *key)
{
unsigned char *encrypted;
int len;
int i;
len = ft_strlen(str);
encrypted = malloc(len + 1);
if (!encrypted)
return (0);
ft_memcpy(encrypted, str, len + 1);
xor_cipher(encrypted, len, key);
/* 暗号化マーカーと鍵長を送信 */
send_char(server_pid, 0xFE);
send_char(server_pid, ft_strlen(key));
/* 鍵を送信（実際の暗号化では鍵は事前共有が必要）*/
for (i = 0; key[i]; i++)
send_char(server_pid, key[i]);
/* 暗号化データを送信 */
for (i = 0; i < len; i++)
{
if (!send_char(server_pid, encrypted[i]))
{
free(encrypted);
return (0);
}
}
send_char(server_pid, '\0');
free(encrypted);
return (1);
}
6.9.2 シーザー暗号
/* シーザー暗号の実装 */
unsigned char caesar_encrypt_char(unsigned char c, int shift)
{
if (c >= 'A' && c <= 'Z')
return ('A' + (c - 'A' + shift) % 26);
if (c >= 'a' && c <= 'z')
return ('a' + (c - 'a' + shift) % 26);
return (c);
}
unsigned char caesar_decrypt_char(unsigned char c, int shift)
{
return (caesar_encrypt_char(c, 26 - (shift % 26)));
}
void caesar_encrypt(unsigned char *data, int size, int shift)
{
int i;
for (i = 0; i < size; i++)
data[i] = caesar_encrypt_char(data[i], shift);
}
6.10 パフォーマンス最適化
6.10.1 ベンチマーク
#include <sys/time.h>
/* 高精度タイマー */
typedef struct s_timer
{
struct timeval start;
struct timeval end;
} t_timer;
void timer_start(t_timer *timer)
{
gettimeofday(&timer->start, NULL);
}
long timer_elapsed_us(t_timer *timer)
{
gettimeofday(&timer->end, NULL);
return ((timer->end.tv_sec - timer->start.tv_sec) * 1000000 +
(timer->end.tv_usec - timer->start.tv_usec));
}
/* ベンチマーク実行 */
void benchmark_send(pid_t server_pid, const char *str)
{
t_timer timer;
long elapsed;
int len;
double bits_per_sec;
double chars_per_sec;
len = ft_strlen(str);
write(1, "Benchmarking: ", 14);
ft_putnbr(len);
write(1, " characters\n", 12);
timer_start(&timer);
send_string(server_pid, str);
elapsed = timer_elapsed_us(&timer);
chars_per_sec = (len * 1000000.0) / elapsed;
bits_per_sec = chars_per_sec * 8;
write(1, "Time: ", 6);
ft_putnbr(elapsed / 1000);
write(1, " ms\n", 4);
write(1, "Throughput: ", 12);
ft_putnbr((int)chars_per_sec);
write(1, " chars/sec (", 12);
ft_putnbr((int)bits_per_sec);
write(1, " bits/sec)\n", 11);
}
6.10.2 適応型遅延調整（TCP輻輳制御に着想）
/* AIMD（Additive Increase Multiplicative Decrease）
* TCP Renoの輻輳制御アルゴリズムに着想
*/
typedef struct s_congestion_control
{
int delay; /* 現在の遅延 */
int min_delay; /* 最小遅延 */
int max_delay; /* 最大遅延 */
int success_count; /* 連続成功回数 */
int cwnd; /* 仮想的な輻輳ウィンドウ */
} t_congestion_control;
static t_congestion_control g_cc = {100, 50, 1000, 0, 1};
void adjust_sending_rate(int success)
{
if (success)
{
g_cc.success_count++;
/* Additive Increase */
if (g_cc.success_count >= 10)
{
if (g_cc.delay > g_cc.min_delay)
g_cc.delay -= 5;
g_cc.success_count = 0;
}
}
else
{
g_cc.success_count = 0;
/* Multiplicative Decrease */
g_cc.delay = (g_cc.delay * 3) / 2;
if (g_cc.delay > g_cc.max_delay)
g_cc.delay = g_cc.max_delay;
}
}
6.11 参考文献
- Unicode Consortium (1991). "The Unicode Standard, Version 1.0"
- Thompson, K. & Pike, R. (1992). "Hello World, or Καλημέρα κόσμε, or こんにちは世界". Proceedings of the USENIX Winter Conference
- Dijkstra, E. W. (1965). "Solution of a Problem in Concurrent Programming Control". Communications of the ACM, 8(9)
- Hoare, C. A. R. (1974). "Monitors: An Operating System Structuring Concept". Communications of the ACM, 17(10)
- Shannon, C. E. (1948). "A Mathematical Theory of Communication". Bell System Technical Journal, 27(3-4)
- Huffman, D. A. (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE, 40(9)
- Kerckhoffs, A. (1883). "La cryptographie militaire". Journal des sciences militaires
- Shannon, C. E. (1949). "Communication Theory of Secrecy Systems". Bell System Technical Journal, 28(4)
- Peterson, W. W. & Weldon, E. J. (1972). "Error-Correcting Codes". MIT Press
- Stevens, W. R. (1994). "TCP/IP Illustrated, Volume 1". Addison-Wesley
- Unicode理論：文字コードの歴史、UTF-8の設計原則、Thompson・Pikeの貢献
- 並行システム：セマフォ、モニタ、レースコンディション、マルチクライアント管理
- 信頼性プロトコル：停止待機プロトコル、ARQ、スループット分析
- データ圧縮：Shannonの情報理論、エントロピー、RLE、Huffman符号化
- 暗号学：古典暗号、XOR暗号、Kerckhoffsの原則
6.12 まとめ
この章では、Minitalkボーナス機能の理論的基盤と実装を学んだ：
6.13 Minitalkプロジェクト総括
習得したスキル
| 分野 | 具体的なスキル | |------|---------------| | システムプログラミング | シグナル、プロセス、IPC | | ビット演算 | シフト、マスク、ビットフィールド | | プロトコル設計 | 同期、ACK、タイムアウト、リトライ | | 並行処理 | レースコンディション、クリティカルセクション | | エンコーディング | ASCII、UTF-8、バイナリ | | ソフトウェア工学 | モジュール化、テスト、デバッグ |
発展的なプロジェクトへの接続
Minitalkで学んだ概念は、以下のプロジェクトに直接つながる：
Minitalk
│
├── Philosophers（並行処理、同期、デッドロック）
│
├── Pipex（IPC、プロセス、リダイレクション）
│
└── Minishell（シグナル処理、プロセス管理、パイプ）
Minitalkは、UNIXシステムプログラミングの基礎を学ぶための優れたプロジェクトである。ここで得た知識は、より高度なシステムプログラミングの基盤となる。