Namaran

Code daily. Without assist.

2026-10-16

redelivery.cpp

#include <cstdint>
#include <iostream>
#include <vector>

struct Event {
    std::uint8_t seq;
    char path;
};

int main() {
    std::vector<Event> events = {{254, 'a'}, {255, 'b'}, {255, 'b'}, {0, 'c'}, {1, 'd'}};
    std::uint8_t last = 253;
    for (const Event& e : events) {
        if (e.seq <= last) {
            continue;
        }
        last = e.seq;
        std::cout << e.path;
    }
    std::cout << '\n';
}

ファイル変更の通知を順に処理し、再送された通知を読み飛ばすつもりのループです。通知元は通知ごとに8ビットの通し番号 seq を1ずつ増やして付け、255 の次は 0 に戻ります。入力は events の5件で、3件目は2件目の再送です。いまの出力は ab です。本来の出力は abcd です。

Answer

Wrong

if (e.seq <= last) {

b を処理した時点で last は 255 です。次の c の番号は 255 の次の 0 ですが、0 <= 255 は真なので再送とみなされて捨てられ、d の 1 も同じ理由で捨てられます。last は 255 のまま更新されないので、このあと届く通知はすべて 255 以下で、一つも処理されません。番号が一周した瞬間から、変更の監視が黙って止まります。

比べ方を差に変えて e.seq - last <= 0 としても直りません。std::uint8_t どうしの引き算は、両方が int に変換されてから行われるので、0 - 255 は -255 になり、やはり 0 以下です。

Right

if (static_cast<std::int8_t>(e.seq - last) <= 0) {

番号は 256 で割った余りとしてしか意味を持たないので、新旧は差を 256 で割った余りで判断します。2つの整数の差が 256 の倍数であることを、256 を法として合同(congruent modulo 256)といいます。int の -255 を std::int8_t に変換すると、-255 と合同な値のうち -128 以上 127 以下に収まる 1 になります1。差が 1 から 127 なら新しい通知、0 なら同じ通知、-128 から -1 なら古い通知として扱えるので、c と d は新しい通知として処理され、再送の b は差が 0 で捨てられます。この判定は、届く順序のずれが 127 件以内に収まることを前提にしています2。

  1. 符号付き整数への変換で値が範囲に収まらないときの結果は、C++17 までは処理系定義でした。C++20 から、変換先のビット数を N として、2 の N 乗を法として合同な値になると規格で決まっています。
  2. 一周する通し番号をこの形で比べる方法は、RFC 1982 で serial number arithmetic として定められており、TCP のシーケンス番号の比較も同じ考え方です。