問題タブ [patch]

C# でのバイナリ パッチ生成アルゴリズムの実装を持っている、または知っている人はいますか?

基本的に、2 つのファイル ( oldとnewで指定) を比較し、古いファイルをアップグレードして新しいファイルと同じ内容にするために使用できるパッチ ファイルを作成します。

実装は比較的高速で、巨大なファイルを処理する必要があります。O(n) または O(logn) ランタイムを示す必要があります。

私自身のアルゴリズムは、お粗末 (高速だが巨大なパッチを生成する) または遅い (小さなパッチを生成するが O(n^2) ランタイム) 傾向があります。

実装のためのアドバイスや指針があればいいでしょう。

具体的には、この実装は、1 つのマスター サーバーを持つさまざまな大きなデータ ファイルに対してサーバーの同期を維持するために使用されます。マスター サーバーのデータファイルが変更されると、いくつかのオフサイト サーバーも更新する必要があります。

私が作成した最も単純なアルゴリズムは、メモリに保持できるファイルに対してのみ機能します。次のとおりです。

1. 古いファイルから最初の 4 バイトを取得し、これをキーと呼びます
2. これらのバイトを辞書に追加します。ここで、key -> position、positionは、これらの 4 バイトを取得した位置であり、最初は 0 です
3. これらの 4 バイトの最初をスキップし、別の 4 バイト (3 重複、1 1) を取得し、同じ方法で辞書に追加します。
4. 古いファイルのすべての 4 バイト ブロックに対して、手順 1 ～ 3 を繰り返します。
5. 新しいファイルの先頭から4 バイトを取得し、辞書で調べます。
6. 見つかった場合は、2 つのファイルのバイトを比較して、複数ある場合は最長の一致を見つけます。
7. 古いファイルでその場所への参照をエンコードし、新しいファイルで一致したブロックをスキップします
8. 見つからない場合は、新しいファイルから 1 バイトをエンコードし、スキップします
9. 新しいファイルの残りの部分について、手順 5 ～ 8 を繰り返します。

これは、ウィンドウ処理を行わない圧縮に似ているため、大量のメモリを使用します。ただし、コード出力を最小限に抑えようとする限り、かなり高速で、非常に小さなパッチが生成されます。

よりメモリ効率の良いアルゴリズムはウィンドウ処理を使用しますが、はるかに大きなパッチ ファイルを生成します。

上記のアルゴリズムには、この投稿では省略したニュアンスが他にもありますが、必要に応じて詳細を投稿できます。ただし、まったく別のアルゴリズムが必要であると感じているため、上記のアルゴリズムを改善しても、おそらく十分ではありません。

編集＃1：上記のアルゴリズムのより詳細な説明は次のとおりです。

まず、2 つのファイルを結合して、1 つの大きなファイルを作成します。2 つのファイル間のカットポイントを覚えておいてください。

次に、4 バイトを取得し、その位置をファイル全体のすべてのディクショナリ ステップに追加します。

3 番目に、新しいファイルの開始位置から、既存の 4 バイトの組み合わせを探してループを実行し、最長の一致を見つけます。古いファイルの位置、または新しいファイルの現在の位置より前の位置のみを考慮するようにしてください。これにより、パッチの適用中に古いファイルと新しいファイルの両方でマテリアルを再利用できます。

編集＃2：上記のアルゴリズムのソースコード

証明書に問題があるという警告が表示される場合があります。それを解決する方法がわからないので、当面は証明書を受け入れます。

ソースは、ライブラリの残りの部分から他の多くの型を使用しているため、必要なのはファイルだけではありませんが、それがアルゴリズムの実装です。

@lomaxx、xdeltaと呼ばれるsubversionで使用されるアルゴリズムの優れたドキュメントを見つけようとしましたが、アルゴリズムの仕組みをまだ知らない限り、見つけたドキュメントは私が知る必要があることを教えてくれません。

それとも、私は単に密集している... :)

いただいたサイトのアルゴリズムをざっと見てみましたが、残念ながら使えません。バイナリ差分ファイルからのコメントは次のように述べています。

最適な差のセットを見つけるには、入力サイズに対して二次時間が必要になるため、すぐに使用できなくなります。

ただし、私のニーズは最適ではないため、より実用的なソリューションを探しています。

答えてくれてありがとう、必要に応じて彼のユーティリティにブックマークを追加しました。

編集＃1：注意してください、私は彼のコードを見て、いくつかのアイデアを見つけることができるかどうかを確認します。また、後で質問をメールで送信しますが、彼が参照している本を読みましたが、解決策は良いです最適なソリューションを見つけるには、時間がかかるため実用的ではありません。

編集＃2：私は間違いなくpython xdeltaの実装を追い詰めます。

(ソース) パッチ ファイルが与えられた場合、Windows でソース ファイルにこのパッチを適用する最も簡単な方法は何ですか?

変更されていないソース行を視覚的に比較できる GUI ツールがあればすばらしいでしょう。

diffのような一時ファイルを無視するにはどうすればよいfoo.c~ですか? 一時的なものをデフォルトで無視する構成ファイルはありますか?

より一般的に: tarball から「クリーンな」パッチを生成する最良の方法は何ですか? 私はこれを行うことはめったにありません (電子メールで OSS プロジェクトにバグ修正を提出する) ので、常に苦労しています...

編集：わかりました、短い答えは

より良い答えはありますか？たとえば、これは構成ファイルに入れることができますか?

プログラムを終了し、終了するプログラムから追加のコードを実行する最良の方法は何ですか? たとえば、プログラムが自分自身を自己更新するための最良の方法は何でしょうか?

SubVersion でのパッチの作成は非常に簡単です。Tortoise では、右クリックして [パッチの作成] を選択します。しかし、私の人生では、TFS でこの機能を見つけることができません。これは可能ですか？

そうでない場合、オープン ソース TFS でホストされているプロジェクト (CodePlex 風) でパッチを送信する標準的な方法は何ですか?

複数の Windows サーバーがある環境で、すべてのシステムでパッチのコンプライアンスを確保するための最善の方法は何ですか?

すべてのシステムのステータスを示すレポートを生成して、監査のたびに各システムを手動でチェックすることなく、自動的にパッチを適用していないシステムを修正できるシンプルなツール (ある種のクライアント/サーバー アプリ?) はありますか?必要ですか？

私がいつも疑問に思っていることの1つは、ソフトウェアパッチがどのように機能するかです。多くのソフトウェアは、古いバージョンの上にインストールする必要があるバイナリで新しいバージョンをリリースするだけのようですが、一部のソフトウェア（特にWindowsなどのオペレーティングシステム）は、バグを修正したり、既存の機能に機能を追加したりする非常に小さなパッチをリリースできるようです。ソフトウェア。

ほとんどの場合、私が目にするパッチは、アプリケーション全体、またはアプリケーション内で使用される小さなファイルを置き換えることはできません。私には、実際のバイナリが変更されているように見えます。

これらの種類のパッチは実際にどのように実装されていますか？これがどのように機能するかを説明するリソースを誰かに教えてもらえますか、それともアプリケーション内のリンクされたライブラリなどの小さなコンポーネントを置き換えるのと同じくらい簡単ですか？

この方法で展開を行う必要はおそらくないでしょうが、それがどのように機能するかを知りたいと思います。パッチが実際にバイナリファイルの一部しか変更できないという私の理解が正しければ、これは.NETで実行できますか？それが私が最もよく知っているフレームワークであり、それがどのように機能するかを理解したいので、それを学びたいと思います。

ソース管理としてSubversionを使用するオープンソースプロジェクトにいくつかのローカル変更があります。（元のプロジェクトリポジトリへのコミットアクセス権がありません。）

私の変更はファイルを追加しますが、このファイルは「svndiff」の出力に含まれていません。（新しいファイルはプレーンテキストではなく、バイナリであることに注意してください。）

新しいファイルを含むパッチを作成するにはどうすればよいですか？

ライブラリ ( NetHooker )の一部としてネットワーク トラフィックをリダイレクトするように connect() にパッチを適用していますが、これはうまく機能しますが、ws2_32.dll が同じままであることに依存し、syscall が直接使用されている場合は機能しません。だから私が疑問に思っているのは、ドライバーなしでシステムコール自体をキャッチする方法があるかどうかです。これが可能かどうか知っている人はいますか？

「パッチの送信」を指す場合、パッチという言葉は正確にはどういう意味ですか？

特にオープンソースの世界では、これがよく使われているのを見てきました。それはどういう意味で、パッチの提出には正確に何が関係していますか？