Unicode 3.13 標準のCaseアルゴリズムの翻訳
Unicodeの文章の、Caseに関するものの翻訳を載せます。
翻訳元は下記の通り。
Unicode Consortium
https://home.unicode.org/
Unicode® 15.0.0
https://www.unicode.org/versions/Unicode15.0.0/
Chapter 3, Conformance
https://www.unicode.org/versions/Unicode15.0.0/ch03.pdf
3.13 Default Case Algorithms
注意点
翻訳者は素人なので、翻訳した内容はでたらめです。
安易に信じないでください。
アルファベットには大文字と小文字が存在します。
そのことを英語でCaseと呼びます。
しかし日本語には対応する語がないようなので、
翻訳ではCaseとそのまま表現しました。
3.13 標準のCaseアルゴリズム
この章では、Caseの変換、Caseの検出、 そしてCaseに依存しないマッチについての 標準アルゴリズムについて述べます。 Caseの対応についてのデータの情報は、 Section 4.2, Caseをご確認ください。 Caseの対応の操作についての一般的な話題は、 Section 5.18, Caseの対応をご確認ください。
ここで紹介する全ての仕様は論理的なものです。 ある特定の実装では、同じ結果をになるようなものとして、 そのプロセスを最適化することができます。
「調整(Tailoring)」。
標準のCase処理とは、特定の言語や環境に対する調整が
必要ない中で使用されることを意図しています。
正しい結果を生成するためにCaseへの処理に
調整が必要であるような特定の環境下において、
そのような調整を使用したとしても
標準の適合に違反することにはなりません。
Unicode文字データベース内のSpecialCasing.txt
というファイルには、
実装への特定の調整を助けるようなデータが記載されています。
例えば次のようなものが含まれます。
SpecialCasing.txt
に含まれるデータではカバーできないような
Caseの調整の例としては次のようなものがあります。
- オランダ語の
IJ
で始まる単語のタイトルCase - ギリシャ語の大文字のアクセントの削除
- タイトルCaseの二文字目か正しいつづりの単語の文字に続くものに含まれる 例えばアポストロフィーのようなCaseのない文字
U+00DF "ß" LATIN SMALL LATTER SHART S
と 大文字のU+1E9E "ẞ" LATIN CAPITAL LETTER SHARP S
の対応
※翻訳者メモ:「タイトルCase」とはTitlecaseのことであり、 大文字で始まり小文字に続く単語の形を意味しています。
Case操作の調整が定義されたもより良い機能として、 Common Locale Data Repository (CLDR)という言うものがあり、 これらの調整は必要に応じて、 例えば言語ごとにベースを指定することができます。
※翻訳者メモ:ここのこと、https://cldr.unicode.org/
Case処理の調整は、望むか望まないかに関わらず、 実装の性質の問題に依存します。 Caseの対応における複雑な話題について、 より詳しくはSection 5.18, Caseの対応をご確認ください。
定義
Unicode文字の完全なCaseの対応は、
SpecialCasing.txt
による対応に加え、
UnicodeData.txt
の対応から、
衝突する文字の対応を除外したものによって得られます。
これらのファイル内に対応がない文字については、
自分自身に対応すると考えます。
文字C
の完全なCaseの対応は、
Lowercase_Mapping(C)
,
Titlecase_Mapping(C)
,
Uppercase_Mapping(C)
のように示されます。
文字C
の完全なCase Foldingの対応は、
Case_Folding(C)
のように示されます。
※翻訳者メモ:Case Foldingとは、Caseに依存しない比較をするときに使うもの。 Caseに依存しない文字列の比較をする際に、 全部大文字や全部小文字で比較するのは色々と問題があるらしい。 このあとで説明がある。
Caseの検出とCaseの対応は、
General_Category
の値(Lu
, Lt
, Ll
)が
ただひとつ以上要求されます。
下記に示す定義が使用されます。
D135
ある文字
C
は、 もしC
が小文字か大文字のプロパティを持っているか、 あるいはGeneral_Category
の値のTitlecase_Letter
を持っているときのみ、 「Caseがある」と定義されます。大文字と小文字のプロパティの値は、 Unicode文字データベースにある
DerivedCoreProperties.txt
という データファイルの中で定義されています。 派生されたCaseのプロパティもまた、DerivedCoreProperties.txt
に列挙されています。
D136
ある文字
C
は、 もしC
がWord_Break
プロパティにおいてMidLetter
(ML
)か、MidNumLet
(MB
)か、Single_Quote
(SQ
)を持っているか、 あるいはGeneral_Category
がNonspacing_Mark
(Mn
)、Enclosing_Mark
(Me
)、Format
(Cf
)、Modifier_Letter
(Lm
)、Modifier_Symbol
(Sk
) のうちのどれかであるときは、 「Caseが無視できる」と定義されます。Word_Break
プロパティは、 Unicode文字データベースのWordBreakProperty.txt
というデータファイルで定義されています。派生されたプロパティである
Case_Ignorable
は、 Unicode文字データベースのDerivedCoreProperties.txt
というデータファイルに 列挙されています。Case_Ignorable
プロパティは、 Table 3-17の文脈の仕様内で使用するために定義されています。 これは狭い範囲での使用目的のプロパティであり、 他の文脈で使用されることを意図していません。 より広く文字列に適用できるCaseの関数isCased(X)
は、D143で定義されています。
D137
- Caseが無視できる列とは、 ゼロか、それ以上のCaseが無視できる文字の列を意味します。
D138
- ある文字
C
が、Table 3-17にあるような 仕様にマッチするときにのみ、 その文字は表中に対応する 特定の文脈依存に対して 「Caseの文脈」の中にあると言えます。
- ある文字
Table 3-17. Caseの文脈仕様
文脈 | 定義 | 正規表現 | |
---|---|---|---|
Final_Sigma |
C は、その前にCaseがある文字があり、さらに0か複数のCaseが無視できる文字が含まれる列が先行しており、かつ、C は、その後に0か複数のCaseが無視できる文字が続かないときは、Caseがある文字とします。 |
C の前 |
\p{cased} (\p{Case_Ignorable})* |
C の後 |
! ( (\p{Case_Ignorable})* \p{cased} ) |
||
After_Soft_Dotted |
C の前にSoft_Dotted 文字があり、介入する文字結合クラスが0か230(上方)がないとき。 |
C の前 |
[\p{Soft_Dotted}] ([^\p{ccc=230} \p{ccc=0}])* |
More_Above |
C は、文字結合クラスが230(上方)に続き、字結合クラス0か230(上方)の介入が無いとき。 |
C の後 |
[^\p{ccc=230}\p{ccc=0}]* [\p{ccc=230}] |
Before_Dot |
C は、COMBINING DOT ABOVE (U+0307)の後に続きます。現在の文字とCOMBINING DOT ABOVE の間にあるどの列の文字も、結合クラスが0ではなく230でもないものであれば介入されるかもしれません。 |
C の後 |
([^\p{ccc=230} \p{ccc=0}])* [\u0307] |
After_I |
大文字I がC の前にあり、結合文字クラス230(上方)か0の介入が無いとき。 |
C の前 |
[I] ([^\p{ccc=230} \p{ccc=0}])* |
※翻訳者メモ:ccc
とは、Canonical_Combining_Class
(結合文字クラス)のこと。
いまは0と230だけ取り上げられているが0~254くらいある。
※翻訳者メモ:230(上方)とは元はccc=230(Above)
みたいな書き方がされており、
文字の上に結合されるもののようです。
このファイルDerivedCombiningClass.txt
に対応がある。
Table 3-17にある各文脈の定義は、
続いて記載されている、
C
の前の文脈か、C
の後の文脈か、あるいはその両方かを定義した
正規表現と同等です。
正規表現はUnicode技術標準#18の「Unicode正規表現」の
構文を使用していますが、
ひとつだけ、!
がその式にマッチしないことを意味する
記号を追加しています。
全ての正規表現は、Caseを考慮します。
Table 3-17にある正規表現の命令である*
は独占的であり、
バックアップなしで多くの文字を消費することができます。
これはFinal_Sigma
の場合では、
Caseが無視できるものとCaseがあるもののそれぞれの文字の集合が
素集合ではないため、重要になります。
例えば、それら両方にU+0345
のypogegrammeni
が含まれます。
したがって、「C
の前」の状況は、
例えばC
がただU+0345
に先行されるだけでは満たされず、
<capital-alpha, ypogegrammeni>
のような列の場合に満たされます。
同様に、「C
の後」の状況では、
C
がただypogegrammeni
のあとに続くときのみ満たされるのであって、
<ypogegrammeni, capital-alpha>
の列によってでは満たされません。
標準のCase変換
下記に示すルールは、Unicode文字列の
標準のCase変換の操作を示しています。
これらのルールは完全なCase変換操作である、
Uppercase_Mapping(C)
,
Lowercase_Mapping(C)
,
Titlecase_Mapping(C)
,
を使用しており、
これらはTable 3-17で示されるCaseの文脈をベースに、
文脈依存のものを対応付けます。
文字列X
に対して、
R1
toUppercase(X)
:X
の中の各文字C
を、Uppercase_Mapping(C)
に対応付けます。R2
toLowercase(X)
:X
の中の各文字C
を、Lowercase_Mapping(C)
に対応付けます。R3
toTitlecase(X)
: Unicode標準付録#29の 「Unicodeテキスト区分」によって対応づけられる、X
中の単語の境界を探します。 単語の各境界において、 その単語の境界に続いて 最初のCaseがある文字F
を探します。 もしF
が存在するとき、Titlecase_Mapping(F)
は、F
と続く単語の境界の間にある 全ての文字C
を、Lowercase_Mapping(C)
に対応付けます。
標準のCase変換操作は、
特定の要求によって調整されるかもしれません。
一般的な調整としては、例えば、
完全なCaseの変換ではなく、
単純なCaseの変換を使用するものがあげられます。
これらのルールは、
言語指定のものや、
locale
指定のものの調整によっても
使用されることがあります。
標準Case Folding
Case Foldingは、Case変換と関係があります。 しかしCase Foldingの主な目的は、 文字列をCaseを考慮せずにマッチを助けることであり、 一方Case変換の主な目的は、 特定のCaseがある形式として文字列を配置することです。
標準Case Foldingは、正規化された形式保持しません。 ある特定の文字列がUnicodeの正規化された形式であったとき、 その文字列は、このCase Foldingされた後では 正規化されたフォームではなくなっているかもしれません。
標準Case Foldingは、
完全なCaseの変換操作がベースになりますが、
文脈依存によるCase文脈へのCaseの対応を行いません。
いくつかの特別なCaseに依存しないマッチに適用するものもあります。
Lowercase_Mapping(C)
は、
多くの文字で使用されますが、
しかしCase Foldingにおいては代わりに
Uppercase_Mapping(C)
をベースとしなければならない例があります。
特にUnicode標準のVersion 8.0では
チェロキー文字の小文字が追加されており、
Case Foldingを安定して成し遂げるために、
それらのチェロキー文字の対となる大文字が
Case Foldingとして共に追加されました。
その結果、Case Fondingの文字列は、
小文字である必要がなくなりました。
ある2つの文字列について、
完全なCase変換である
toUppercase(X)
,
toLowercase(X)
,
toTitlecase(X)
を用いて
お互いにCaseの変換を行うことを考えます。
これらの機能を用いて同じ文字列に対して
Case FoldingをtoCasefold(X)
という操作で定義します。
- R4
toCasefold(X)
:X
の中の各文字C
を、Case_Folding(C)
に対応付けます。Case_Folding(C)
は、Unicode文字データベースのCaseFolding.txt
というデータファイルに示される、 状態のフィールドがC
かF
という値のものと 対応付けるときに使用されます。
標準Case Foldingの修正された形式とは、
識別子として解釈するため
文字列をCaseに依存せずマッチさせるときに
良い動作をするように設計されています。
このCase Foldingは、Case_Folding(C)
をベースにしていますが、
UnicodeのプロパティDefault_Ignorable_Code_Point
の値がTrue
となっている
全ての文字を削除しています。
これは、また文字をNFKC
の同等の列へ対応付けられます。
いちど文字の対応が完了すると、
その結果の文字列は、正規化されたNFC
になります。
この最後の正規化のステップにより、
単純にCaseに依存しないマッチのためのCase Foldingを
使用できる状態になります。
- R5
toNFKC_Casefold(X)
:X
の中の各文字C
を、NFKC_Casefold(C)
に対応付けます。 そしてその結果の文字列はNFC
に正規化されます。
※翻訳者メモ:バイナリプロパティとはboolean形式のものを意味しているようです。
NFKC_Casefold
の使用方法と、
識別子に対するCaseに依存しないマッチについて、
より詳しい情報はUnicode標準付録#31の
「Unicode識別子とパターン構文」をご確認ください。
標準Case検出
文字列のCaseの状態は、
前に定義されたCase操作を使用することによって決定できます。
下記に示す定義は、その仕様を提供します。
これらはX
とY
が文字列であると仮定しています。
下記に示すもので、関数名がis
で始まっているものは、
文字列X
を受け取り、
その文字列が指定されたCaseの状態と
全体でマッチしているときに
true
を返却するバイナリ関数です。
例えば、isLowercase(X)
は、
もし文字列X
の全体が小文字のときtrue
を返却します。
一方Lowercase
のようなUnicode文字のプロパティは、
文字ごとにある個別のプロパティです。
各定義は、
Unicode文字プロパティの名前が
Changes_When_
で始まっているものと関係があります。
これらのプロパティは、
各文字が特定のCase操作によって影響されるものかどうかを示しており、
それは文字列の「標準Case検出」の
実装の最適化として使用することができます。
Case変換が
展開された(あるいはもっと正確には、NFD
へ正規化された)文字列へ
適用されたとき、
文字ごとにCase変換を適用しても、
文字列の正規化状態には影響しません。
したがって、これらの定義は
正規化形式 Normalization Form NFD
という語で定義されます。
この定義を読みやすくするために、
これらの変換の適用を、
文字列Y
と等しいtoNFD(X)
と表します。
D139:
isLowercase(X)
:isLowercase(X)
は、toLowercase(Y) = Y
のときtrue
です。- 例えば、
isLowercase("combining mark")
はtrue
であり、isLowercase("Combining mark")
はfalse
です。 - 派生されたバイナリプロパティの
Changes_When_Lowercased
は、 Unicode文字データベースのDerivedCoreProperties.txt
という データファイルに列挙されています。
- 例えば、
D140:
isUppercase(X)
:isUppercase(X)
は、toUppercase(Y) = Y
のときtrue
です。- 例えば、
isUppercase("COMBINING MARK")
はtrue
であり、isUppercase("Combining mark")
はfalse
です。 - 派生されたバイナリプロパティの
Changes_When_Uppercased
は、 Unicode文字データベースのDerivedCoreProperties.txt
という データファイルに列挙されています。
- 例えば、
D141:
isTitlecase(X)
:isUppercase(X)
は、toTitlecase(Y) = Y
のときtrue
です。- 例えば、
isTitlecase("Combining Mark")
はtrue
であり、isTitlecase("Combining mark")
はfalse
です。 - 派生されたバイナリプロパティの
Changes_When_Titlecased
は、 Unicode文字データベースのDerivedCoreProperties.txt
という データファイルに列挙されています。
- 例えば、
D142:
isCasefolded(X)
:isCasefolded(X)
は、toCasefold(Y) = Y
のときtrue
です。- 例えば、
isCasefolded("heiss")
はtrue
であり、isCasefolded("heiß")
はfalse
です。 - 派生されたバイナリプロパティの
Changes_When_Casefolded
は、 Unicode文字データベースのDerivedCoreProperties.txt
という データファイルに列挙されています。
- 例えば、
Caseがない文字は、
例えば文字列関数であるisLowercase(X)
のような
Case検知操作の結果には影響しません。
したがって、スペースや数は、
文字列の結果には影響に加わりません。
Table 3-18の例では、
これらの状態は互いに排他的ではないことが示されています。
A2
は大文字とタイトルCaseの両方あてはまります。
なぜなら、3
はCaseがないため、
小文字、大文字、タイトルCaseを
同時に満たすからです。
Table 3-18. Case検出の例
Case | 文字 | 名前 | 文字と数 | 数値 |
---|---|---|---|---|
小文字 Lowecase | a |
john smith |
a2 |
3 |
大文字 Lowecase | A |
JOHN SMITH |
A2 |
3 |
タイトル Titlecase | A |
John Smith |
A2 |
3 |
文字列が、例えば123
のように、
Caseがない文字のみ含まれていたとき、
3つの状態である
isLowercase
,
isUppercase
,
isTitlecase
の全てがtrue
に評価されます。
この状態の組み合わせは、
次に続く定義を使用することで、
Caseがある文字の出現をチェックするときに使用できます。
- D143:
isCased(X)
:isCased(X)
は、isLowercase(X)
がfalse
か、isUppercase(X)
がfalse
か、isTitlecase(X)
がfalse
のいずれかのとき、true
です。- ある文字列
X
があるとき、 その中にある文字が 自分自身以外にCaseの対応を持つものが すくなくともひとつ含まれているとき、isCased(X)
はtrue
です。 - 例えば、
isCased("123")
はfalse
であり、 なぜなら123
内にあるすべての文字は それら自身にCaseの対応を持つからです。 また、isCased("abc")
とisCased("A12")
は 両方ともtrue
です。 - 派生されたバイナリプロパティの
Changes_When_Casemapped
は、 Unicode文字データベースのDerivedCoreProperties.txt
という データファイルに列挙されています。
- ある文字列
文字列にただ小文字のみが含まれているかどうかを確認するときは、
実装は(isLowercase(X) and isCased(X))
をテストする必要があります。
標準のCaseに依存しないのマッチ
標準のCaseに依存しないのマッチは、 2つの文字列をCaseを考慮せずに 同一かどうかを比較する処理です。 Unicodeの標準のCaseに依存しないのマッチの定義は、 Unicodeの標準Case Foldingの定義で構築されます。
標準のCaseに依存しないのマッチは、完全なCase Foldingを使用して 下記のように行います。
- D144
文字列X
は、次の条件のときのみ、 文字列Y
に対してCaseに依存しないのマッチが成立します。
toCasefold(X) = toCasefold(Y)
Caseを無視した文字列の同一性の比較を行うとき、
その文字列はより正しい結果のために
正規化する必要があります。
例えば、U+00C5
のÅ
である
latin capital letter a with ring above
の
Case Foldingは、
U+00E5
のå
である
latin small letter a with ring above
であり、
一方では
<U+0041 "A" latin capital letter a, U+030A combining ring above>
という列のCase Foldingは、
<U+0061 "a" latin small letter a, U+030A combining ring above>
です。
単純に両方の文字列のCase Foldingの結果を
二値の比較をするだけでは、
Case Foldingされた文字列の結果と同等の
正規化された列に対しては正しく判定できないかもしれません。
実際にCase Foldingの後で正規化は必要であり、
なぜならCase Foldingは
文字列にあるすべての要素の
正規化形式を保持しないからです。
この正規化の要求は、
次に示す、正規化におけるCaseに依存しないのマッチの
定義で対応されています。
- D145
文字列X
は、次の条件のときのみ、 文字列Y
に対して正規化されたCaseに依存しないのマッチが成立します。
NFD(toCasefold(NFD(X))) = NFD(toCasefold(NFD(Y)))
D145のCase Foldingの前に
呼び出される正規化の分解(NFD正規化)は、
非常にまれなケースを補足するものです。
Case Foldingの前の正規化は要求されるものではありませんが、
例外があり、
文字U+0345 combining greek ypogegrammeni
と、
あとは例えばU+1FC3 greek small letter eta with ypogegrammeni
のような
正規化の分解の一部として使われるような文字があげられます。
実際には、正規化されたCaseに依存しないのマッチは、
これらの特別な場合を補足するための
最適化されたバージョンを使用しますので、
したがって各比較を行うときに余計な正規化のステップを
避けることができます。
いくつかの場合、実装者は 各文字列に対してCaseに依存しない同一性の比較を行うときに、 文字列間の互換性の差異を無視したいと思うかもしれません。 このようなことを行うための正しい方法は、 下記に示す互換性があるCaseに依存しないマッチの定義を使うことです。
- D146
文字列
X
は、次の条件のときのみ、 文字列Y
に対して互換性があるCaseに依存しないのマッチが成立します。
NFKD(toCasefold(NFKD(toCasefold(NFD(X))))) = NFKD(toCasefold(NFKD(toCasefold(NFD(Y)))))
互換性があるCaseに依存しないマッチは、
Case Foldingのサイクルを余分に追加しており、
そして各文字列の正規化を比較するよう要求しています。
なぜなら、
U+3392 square mhz
のような
互換性のある文字の
NFKD
正規化は、
正しく比較するためには
再びCase Folding(あと正規化)を行う必要があるような
アルファベット文字の列が返却されるからです。
識別子へのCaseに依存しないマッチは、
NFKC_Casefold
の対応を使用することによって
単純化と最適化をすることができます。
この対応は
繰り返されたCase FoldingとNKFD
正規化の結果に派生されたものを
内部に組み込んでいます。
また、
プロパティの値がDefault_Ignorable_Code_Point = True
であるような
文字もマップしており、
これらは識別子の比較時に
差異をつくる必要がありません。
下記にCaseに依存しない識別子のマッチの定義を示します。
- D147
文字列
X
は、次の条件のときのみ、 文字列Y
に対してCaseに依存しない識別子のマッチが成立します。
toNFKC_Casefold(NFD(X)) = toNFKC_Casefold(NFD(Y))
C言語でMD5を取得する
1. はじめに
以前、C言語でxorshiftの乱数を使う投稿をしましたが、 その中で乱数の初期値を決めるためだけに MD5を使っていたと話しました。
一応そのファイルの使い方も紹介します。
せっかく作ったんですし、
書いておかないと自分が忘れますので。
でも、C言語でMD5を使うソースなど星の数も無いかもしれませんが、
もっと信頼性の高いものがたくさんあると思いますので、
そちらを使った方がよろしいかと思います。
なんかいつも「他の使えよ」って言ってる気がする。
ファイルはここです。
https://github.com/nptcl/hypd/tree/main/develop/random
- md5encode.c
- md5encode.h
2. ドキュメント
MD5のアルゴリズムは、RFCのやつを見ました。
それしか見てません。
[RFC1321] The MD5 Message-Digest Algorithm
https://www.ietf.org/rfc/rfc1321.txt
なお、上記RFCにはC言語のソースが載ってます。
でもそれを使ってません。
ソースは一切見てません。
ライセンスの都合上、見るわけにはいかなかったのです。
全部自作と言い張ります。
3. 使い方
先に細かい制限を言っておきますが、 入力は全てバイト単位であり、 ビット単位では無理です。
どうもMD5ってビット単位でも受け付けるようです。
私の配布したソースでは無理。
まず文字列を入力としてみましょう。
uint8_t x[MD5ENCODE_SIZE]; string_md5encode("Hello md5encode", x);
これで、配列x
にMD5の値が入ります。
ちなみにMD5ENCODE_SIZE
は16
です。
値を見てみましょう。
int i; for (i = 0; i < MD5ENCODE_SIZE; i++) printf("%02x", x[i]); printf("\n");
結果は下記の通り。
182acd2b34ce893801875f2c201d7547
本当にあっているか確認したいので、 FreeBSDのmd5コマンドを実行してみます。
$ echo -n "Hello md5encode" | md5 182acd2b34ce893801875f2c201d7547
うん、いいですね。
文字列じゃなくて、 好きなバイトの列を入力に入れたいなら次の通り。
uint8_t x[MD5ENCODE_SIZE]; void *ptr; ptr = (void *)"Hello md5encode"; sequence_md5encode(ptr, 15, x);
結果は文字列のときと同じですが、
上記の場合は入力の長さを指定できるので、
バッファの値が文字列の終端を表す0
であっても大丈夫です。
今まで使った関数
string_md5encode
sequence_md5encode
この2つは、入力に単一のバッファのみを受け付けるものでした。
でもストリーム相手にMD5を取得したいときなんかでは使いづらいです。
そうではなく、何度も入力を受け付けて、 最終的に値を返却したい場合は次のようにします。
struct md5encode md5; clear_md5encode(&md5);
これで準備ができました。
構造体のmd5
を使い、
複数の入力を行いましょう。
read_md5encode(&md5, "Hello", 5); read_md5encode(&md5, " ", 1); read_md5encode(&md5, "md5encode", 9);
上記の例は文字列を指定していますが、 ポインタなら何でもいいです。
それでは結果を出してみます。
uint8_t x[MD5ENCODE_SIZE]; calc_md5encode(&md5, x);
これで、配列x
にMD5の値が格納されました。
注意点として、もう一度calc_md5encode
を実行しようとすると、
プロセスごとabort()
しますので注意。
考えてみればそこまですることはなかった。
使い方は以上です。
このコードは、何の目的もなく、なんとなく作った記憶があります。
それが今じゃxorshift専用だぜ!
DEFLATEの展開コードを作る
1. はじめに
C言語でDEFLATEという圧縮アルゴリズムの展開コードを作りました。
ただし次の二点において問題があるためお勧めできません。
- zlibに比べるととても遅い
- 圧縮はまだ作ってない
でも放置すると忘れるのでgithubに登録しました。
自分自身が忘れないためにも周知します。
配布はここです。
https://github.com/nptcl/hypd/tree/main/develop/deflate
2. DEFLATEとはなにか
あまり詳しく説明する気はないのでさらっと行きます。
gzipで使われている、圧縮のアルゴリズムです。
lz77とかハフマン符号とか使われています。
今回配布しているコードでは、それらと真っ向から向き合っています。
RFCで仕様が公開されている所がとてもいいと思います。
https://www.ietf.org/rfc/rfc1951.txt
今回は日本語の翻訳をフルで活用させていただきました。
CGI Perl 専門サイト - futomi's CGI Cafe
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳
https://www.futomi.com/lecture/japanese/rfc1951.html
ありがとうございました!
3. 見どころ
見どころはインターフェイスでしょうか。
展開(あとは一応圧縮も)の構造体に、
入力と出力のバッファを合わせて2つ持っており、
必要になったらバッファの入力と出力をお願いするような形になっています。
簡易的なストリームを作ったことになるので、
まあまあどんな状況にでも使うことができるような感じなのではないでしょうか。
詳しくはそのうち話すかもしれませんが、 今はやる気がないので例を見てくださいでごまかします。
4. そのうちやりたいこと
もう少し展開を早くできると思うのでやりたいです。
あと、圧縮コードは絶対作ります。
いまのコードで圧縮しようとすると、一応DEFLATE形式で生成はするのですが、
何も圧縮しないでそのまま出力するモードで行われます。
DEFLATE(しぼむ)なのにINFLATE(ふくらむ)してしまいます。
面白いですね!!
C言語でUTF-8などを読む
1. はじめに
C言語で、UTF-8などを読み込むコードを作成しました。
これもnptの抜き出しです。
https://github.com/nptcl/hypd/tree/main/develop/unicode
たぶん私だけだと思いますが、
UTF-8の読み込みは本当によく使います。
どれだけ同じようなものを作ったことか。
必要になるたびにnptのコードをコピーして改造して使っていました。
もうそんなのやめたいと思って作ったわけです。
今回のコードができることは、次の二点です。
- ひとつの文字だけ読む
- ひとつの文字だけ書く
主な内容はこれだけです。
しかもコードをコピーしやすくしました。
これで遠慮なくどこにでも貼りつけられる。
2. 使う
例で使用する変数宣言から。
int x; unicode c; struct state_utf8 decode;
使う前に初期化しましょう。
init_utf8(&decode);
ひとつの文字を読み込んでみます。
x = decode_utf8(&decode, 'A', &c); /* x=1, c='A' */
文字が読めたら返却値x
は1
です。
同時に変数c
に結果の文字'A'
が格納されます。
続けて読み込みできます。
x = decode_utf8(&decode, 'B', &c); /* x=1, c='B' */
ちょっと変な文字を読み込んでみましょう。
x = decode_utf8(&decode, 0xF0, &c); /* x=0 */
返却値x
が0
のときは、続けて入力が必要です。
x = decode_utf8(&decode, 0x9F, &c); /* x=0 */ x = decode_utf8(&decode, 0x80, &c); /* x=0 */ x = decode_utf8(&decode, 0x80, &c); /* x=1, c=0x01F000 */
返却値x
が1
になると、読み込んだ文字をc
に格納します。
今の場合は、UTF-8のコードF0 9F 80 80
で、
U+1F000
という文字ができあがります。
ちなみにこの文字は麻雀牌の🀀です。
次のような場合を考えます。
x = decode_utf8(&decode, 0xF0, &c); /* x=0 */ x = decode_utf8(&decode, 0x7F, &c); /* x=-1, ERROR */
2つめの入力0x7F
は正しくないため、
返却値x
はエラーを示す-1
になります。
こうなると、以降の操作は全てエラーになります。
x = decode_utf8(&decode, 'A', &c); /* x=-1, ERROR */
元に戻したいときは初期化しましょう。
init_utf8(&decode); x = decode_utf8(&decode, 'A', &c); /* x=1, c='A' */
ついでに書き込みも説明します。
まずは変数宣言から。
int x, y; uint8_t array[4];
配列array
には、UTF-8のコードが格納されます。
4つもあれば十分です。
それではU+1F000
という文字のUTF-8を求めましょう。
x = encode_utf8(0x1F000, array, &y);
うまくいったときは、返却値x
が0
になります。
変数y
には、配列array
にいくつ書き込んだかを格納します。
今の場合は4byteなので、y=4
です。
コードは下記のようになります。
array[0] = 0xF0 array[1] = 0x9F array[2] = 0x80 array[3] = 0x80
これでUTF-8の入出力はできるようになりました。
C言語でxorshiftの乱数を使う
1. はじめに
C言語でxorshiftという乱数発生を使うコードを作成しました。
前回のeastasian
と同じように、nptから抜き出したものです。
配布はここ。
https://github.com/nptcl/hypd/tree/main/develop/random
最初にひどいことを言っておきますが、
私はこの分野の専門家ではないので、
このモジュールを使う利点は一切ないと思います。
こういう自分に自信のない書き込みというのはとても良くないとは思うのですが、
数値計算に関係するものならはっきり言っておきます。
何か問題が起きてからではどうしようもありません。
使うなら十分注意してくださいね。
使用するファイルは下記の通り。
- random.c
- random.h
- md5encode.c
- md5encode.h
md5encode.cは、単にMD5を計算するコードです。
xorshiftの初期値を計算するときのためだけに登録しました。
贅沢ですね。
2. コンパイル
コンパイルの方法は少し面倒です。
乱数の初期値を取得するために、OSを指定しなければなりません。
Unix, Linux, FreeBSDの場合は、次のようにしてください。
$ cc -DHYPD_UNIX -c random.c $ cc -DHYPD_LINUX -c random.c $ cc -DHYPD_FREEBSD -c random.c
上記3行は全部同じであり、
乱数の初期値を設定する際に/dev/urandom
を読み込もうとします。
一方、Windows版も用意されています。
HYPD_WINDOWS
をdefine
してください。
# シェルでの実行例 $ cc -DHYPD_WINDOWS -c random.c
こちらは、advapi32.dll
のSystemFunction036
という関数、
通称RtlGenRandom
を使用して乱数の初期値を指定するようになります。
それ以外の場合でもコンパイルはできます。
$ cc -c random.c
ただし初期状態は、現在の時刻であったり、関数のポインターであったり、
極力努力はしますが、全然信頼できない初期値になりますので注意してください。
一応/dev/urandom
を読み込もうとはしますが、
無かったら諦めた上で成功したことにしますので注意。
3. 使い方
使い方を説明します。
uint64_t x; struct random_state state; random_seed_string(&state, "Hello"); x = random_number_64bit(&state);
これで、変数x
には乱数が返却されます。
変数state
には、乱数の内部状態が格納されます。
まずはrandom_seed_string
関数を用いて、
Hello
という文字列で内部状態を初期化します。
ここの文字列は何でもいいです。
そのあと、Hello
に設定された内部状態を用いて、
random_number_64bit
により64bitの乱数を計算して返却します。
返却値を見てみましょう。
int main(void) { uint64_t x; struct random_state state; random_seed_string(&state, "Hello"); x = random_number_64bit(&state); printf("0x%" PRIX64 "\n", x); x = random_number_64bit(&state); printf("0x%" PRIX64 "\n", x); x = random_number_64bit(&state); printf("0x%" PRIX64 "\n", x); return 0; }
出力結果は下記の通り。
0x6D16DA894C444233 0x7C8C640A1AD04940 0xBB5BBF5B4EF005AE
この結果は、どの環境でも同じになると思います。
何度実行しても同じ値になります。
別の乱数列を生成させたい場合は内部状態の初期値を変更します。
random_seed_string(&state, "AAABBB"); x = random_number_64bit(&state);
これで、内部状態AAABBB
に対応する乱数列が生成されるようになります。
内部状態の設定は、文字列以外でも設定できます。
バッファを直接流し込んでみましょう。
random_seed_buffer(&state, "Hello", 5);
第1引数に内部状態、
第2引数にバッファのポインタ、
第3引数にバッファのサイズを指定します。
これは、
random_seed_string(&state, "Hello");
と同じですね。
あとは、OS依存になるのですが、 でたらめな内部状態を設定することもできます。
if (random_seed_randomly(&state)) { fprintf(stderr, "random_seed_randomly error.\n"); exit(1); }
このように設定すると、変数state
にはいつも違った値が設定されます。
つまり、実行するたびに違う乱数値が生成されるようになります。
ただしこれが利用できるのは一部の環境のみです。
詳しくはコンパイルの方法で説明しました。
乱数が生成されたのはいいのですが、
値の範囲が大きすぎて使いづらくて仕方がありません。
例えば、0
から10
までの値を取得したいときはどうしたらいいでしょうか。
間違っても%
で余りを求めたらいけませんよ。
下記のように実行します。
x = random_equal_64bit(&state, 10);
ちなみに、次のようにも書けます。
x = random_less_64bit(&state, 11);
境界の10
と11
が含まれるか含まれないかの違いなので、
どちらを使ってもいいです。
最後に浮動小数の乱数生成について説明します。
float a; double b; long double c; random_seed_string(&state, "Hello"); a = float_random_64bit(&state); b = double_random_64bit(&state); c = long_random_64bit(&state);
変数a
, b
, c
には、
それぞれの型に対応する乱数が代入されます。
値の範囲は、0.0
(含む)から1.0
(含まれない)までです。
つまり0.0~0.9999...
の乱数値です。
何でこんな範囲になったのかはANSI Common Lispの都合だと思います。
4. その他の情報
関数の名前が_64bit
で終わっているものがあるのですが、
_32bit
も用意されています。
違いは色々あるのですが些細なことなので、
全部_64bit
だけでいいと思います。
たぶん返却値の型がuint32_t
とuint64_t
という
違いだけなのでしょう。
変数state
は乱数の内部状態であり、
128bit長の整数が保存されています。
関数random_seed_string
とrandom_seed_buffer
は、
その引数からMD5を経由してstate
の値を決定します。
何も文字列やバッファなんか使わなくても、 直接値を格納する方法もあります。
struct random_state state; state.seed.u64[0] = 100; state.seed.u64[1] = 200;
あるいはこんな感じ。
struct random_state state; state.seed.u32[0] = 300; state.seed.u32[1] = 400; state.seed.u32[2] = 500; state.seed.u32[3] = 600;
逆に言うなら、これらの値を保存しておけば、 いつでもその時の乱数列を再現できるというわけです。
C言語でEast Asian Widthを調べる
1. はじめに
C言語でEast Asian Widthを調べるコードを作りました。
作ったといってもnptのソースから抜き出しただけですが。
配布はここ。
https://github.com/nptcl/hypd/tree/main/develop/eastasian
ある機能がnpt内だけで使えるというのは個人的に不便だったので、 いくつかの機能を分離させて登録することにしました。
East Asian Widthとは、全角/半角のUnicode版です。
「あ
」という文字は全角で、「A
」という文字は半角です。
しかし「A
」という文字は全角になります。
ブラウザによっては見づらいかもしれません。
ファイルは下記の通り。
- eastasian.c
- eastasian.h
- unicode.h
このうちunicode.h
はダミーファイルの位置づけであり、
あとでUnicodeを操作する本物のファイルをどこかに登録する予定です。
ダミーの内容はtypedef int32_t unicode;
だけです。
2. 使い方
使い方は簡単です。
unsinged x; x = eastasian_width('A');
「A
」は半角なので、x
には1
が入ります
x = eastasian_width(0x3042); /* あ */
「あ
」は全角なので、x
は2
が入ります。
East Asian Widthというのは、全角と半角だけではなく、
種類がいくつかあります。
いったい何の種類なのかを調べたいときはeastasian_symbol
関数を使用します。
enum EastAsianType y; y = eastasian_symbol('A');
「A
」はNa
という型なので、y
にはEastAsian_Na
が入ります。
y = eastasian_symbol(0x3042); /* あ */
「あ
」はW
という型なので、y
にはEastAsian_W
が入ります。
返却される種類は下記の通り。
EastAsian_error EastAsian_N EastAsian_A EastAsian_H EastAsian_W EastAsian_F EastAsian_Na
このうち、どの種類が全角なのか、あるいは半角なのかは、
いろんな都合で違っているようです。
一応変更できるようにしています。
初期値に戻すinit_eastasian
関数を見てみましょう。
void init_eastasian(void) { EastAsianSymbol[EastAsian_error] = 0; EastAsianSymbol[EastAsian_N] = 1; EastAsianSymbol[EastAsian_A] = 2; EastAsianSymbol[EastAsian_H] = 1; EastAsianSymbol[EastAsian_W] = 2; EastAsianSymbol[EastAsian_F] = 2; EastAsianSymbol[EastAsian_Na] = 1; }
こんな感じで自由に変えてください。
EastAsianSymbol
はグローバル変数の配列です。
eastasian_width
関数はこの変数を見ます。
スレッド使ってるからグローバル変数なんて使いたくないやって方は、
eastasian_symbol
関数で種類を取って自分で判定してください。
3. 技術的なこと
East Asian Widthの値は、Unicodeの本家でファイルとして配布されています。
具体的にはここです。
http://www.unicode.org/Public/UNIDATA/EastAsianWidth.txt
このファイルを読み込み、C言語のソースを直接出力しました。
それをやっているのがmake/hypd.eastasian.lisp
です。
Common Lispで作成してあります。
ファイルの内容はまあまあ大きいので、
調べたい文字を頭から順に探索するわけにはいきません。
かといってUnicodeの全文字を配列にするのも
メモリがもったいないなという気がしたので、
C言語のソースにはソートした内容を出力し、
それを二分探索して型を調べています。
二分探索なのでまあまあ早いのですが、
最速ではないということだけは覚えておいてください。
ちなみに文字コード0x00
から0x80
までは配列に格納されているので
調べるのは一瞬です。
Dictionaryの翻訳完了とバグ報告
ANSI Common LispのDictionaryの翻訳が終わりました。
トップはここ。
https://nptcl.github.io/npt-japanese/md/ansicl/index.html
気が向いたらformat
の構文のところだけ翻訳するかもしれません。
~A
の使い方とかいつもいつも自分が困ってるんで。
翻訳してた時にnpt
のバグもいくつか見つけました。
適当に列挙します。
バグ
defparameter
,defvar
はコンパイル時に副作用してはいけないcompiler-macro
はnotinline
で禁止できるsxhash
は循環構造があっても終了しなければならないdescribe
で循環構造を見つけなければならない- 数学関数のブランチカット全部見直し
compile
時の副作用見直し- (もっとあったはずだけどメモしてなかった、また何度か見直すと思う)
なんとかしたい
inline
,notinline
,dynamic-extent
を何とかしたい- Metaobject Protocolなんとかしたい(★優先度高い)
inspect
をちゃんと作れば面白そう
影響が大きすぎて嫌になるバグ
- たぶん
condition
かrestart
が起きたタイミングでgc
起動するといろんな箇所でメモリ破壊が生じると思う
- たぶん
その他
- あともっとあったらここを更新していきます。
今後はnpt
の開発に戻ります。
飽きるまで次のことをちゃんとやっていきます。
- Metaobject Protocol
eval
,compile-file
- ブランチカット
なんにせよ翻訳が完成できてよかった。
ようやくプログラミングに戻れる。