nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

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というファイルには、 実装への特定の調整を助けるようなデータが記載されています。 例えば次のようなものが含まれます。

  • トルコ語のドットが付与された大文字のIとドットがない小文字iのCaseの規則
  • リトアニア語の追加のアクセント文字である i上にドットをつけるCaseの規則

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に正規化されます。
    • NFKC_Casefold（短縮形NFKC_CF）は、 Unicode文字データベースのDerivedNormalizationProps.txtという データファイルに定義されています。
    • 派生されたバイナリプロパティであるChanges_When_NFKC_Casefoldedもまた、 Unicode文字データベースのDerivedNormalizationProps.txtという データファイルに列挙されています。

※翻訳者メモ：バイナリプロパティとは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を取得する

C言語

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の展開コードを作る

C言語

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などを読む

C言語

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の乱数を使う

C言語

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を調べる

C言語

1. はじめに

C言語でEast Asian Widthを調べるコードを作りました。
作ったといってもnptのソースから抜き出しただけですが。

配布はここ。

https://github.com/nptcl/hypd/tree/main/develop/eastasian

ある機能がnpt内だけで使えるというのは個人的に不便だったので、 いくつかの機能を分離させて登録することにしました。

East Asian Widthとは、全角／半角のUnicode版です。
「あ」という文字は全角で、「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の翻訳完了とバグ報告

Common Lisp

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
  • ブランチカット

なんにせよ翻訳が完成できてよかった。
ようやくプログラミングに戻れる。