Anhang C. Pseudocode

Die Wohlgeformtheit eines CBOR-Elements kann mit dem Pseudocode in Abbildung 1 geprüft werden. Die Daten sind genau dann wohlgeformt, wenn:

• der Pseudocode nicht "fail" ausführt;

• nach Ausführung des Pseudocodes keine Bytes in der Eingabe übrig bleiben (außer bei Streaming-Anwendungen)

Der Pseudocode hat die folgenden Voraussetzungen:

• take(n) liest n Bytes aus den Eingabedaten und gibt sie als Byte-Zeichenfolge zurück. Wenn keine n Bytes mehr verfügbar sind, schlägt take(n) fehl.

• uint() wandelt eine Byte-Zeichenfolge in eine vorzeichenlose ganze Zahl um, indem die Byte-Zeichenfolge in Netzwerk-Byte-Reihenfolge interpretiert wird.

• Arithmetik funktioniert wie in C.

• Alle Variablen sind vorzeichenlose ganze Zahlen mit ausreichendem Wertebereich.

well_formed (breakable = false) {
  // process initial bytes
  ib = uint(take(1));
  mt = ib >> 5;
  val = ai = ib & 0x1f;
  switch (ai) {
    case 24: val = uint(take(1)); break;
    case 25: val = uint(take(2)); break;
    case 26: val = uint(take(4)); break;
    case 27: val = uint(take(8)); break;
    case 28: case 29: case 30: fail();
    case 31:
      return well_formed_indefinite(mt, breakable);
  }
  // process content
  switch (mt) {
    // case 0, 1, 7 do not have content; just use val
    case 2: case 3: take(val); break; // bytes/UTF-8
    case 4: for (i = 0; i < val; i++) well_formed(); break;
    case 5: for (i = 0; i < val*2; i++) well_formed(); break;
    case 6: well_formed(); break;     // 1 embedded data item
  }
  return mt;                    // finite data item
}

well_formed_indefinite(mt, breakable) {
  switch (mt) {
    case 2: case 3:
      while ((it = well_formed(true)) != -1)
        if (it != mt)           // need finite embedded
          fail();               //    of same type
      break;
    case 4: while (well_formed(true) != -1); break;
    case 5: while (well_formed(true) != -1) well_formed(); break;
    case 7:
      if (breakable)
        return -1;              // signal break out
      else fail();              // no enclosing indefinite
    default: fail();            // wrong mt
  }
  return 0;                     // no break out
}

Abbildung 1: Pseudocode für die Prüfung der Wohlgeformtheit

Hinweis: Die verbleibende Komplexität eines vollständigen CBOR-Decoders besteht darin, die geparsten Daten der Anwendung in einer geeigneten Form bereitzustellen.

Die Haupttypen 0 und 1 sind so gestaltet, dass sie in C aus einer vorzeichenbehafteten ganzen Zahl kodiert werden können, ohne tatsächlich eine if-then-else-Unterscheidung für positiv/negativ vorzunehmen (Abbildung 2). Dabei wird die Tatsache genutzt, dass (-1-n), die Transformation für Haupttyp 1, in der vorzeichenlosen Arithmetik von C gleich ~n (bitweises Komplement) ist; ~n kann dann im negativen Fall als (-1)^n ausgedrückt werden, während 0^n im nicht-negativen Fall n unverändert lässt. Das Vorzeichen einer Zahl kann in -1 für negative und 0 für nicht-negative (0 oder positive) Werte umgewandelt werden, indem die Zahl um einen Bit weniger als ihre Bitlänge arithmetisch verschoben wird (beispielsweise um 63 bei 64-Bit-Zahlen).

void encode_sint(int64_t n) {
  uint64t ui = n >> 63;    // extend sign to whole length
  mt = ui & 0x20;          // extract major type
  ui ^= n;                 // complement negatives
  if (ui < 24)
    *p++ = mt + ui;
  else if (ui < 256) {
    *p++ = mt + 24;
    *p++ = ui;
  } else
       ...

Abbildung 2: Pseudocode für die Kodierung einer vorzeichenbehafteten ganzen Zahl