Bitweisen vertikalen Counter auswerten

[Christoph B. (nuke)]

Hallo allerseits,

da mein Gehirn schon einen Knoten hat, hoffe ich, dass einer von euch 
eine gute Idee hat zu folgender Knobelaufgabe:

Ich habe mir für meinen Algorithmus (an der Stelle unwichtig) einen 
"vertikalen" Counter gebaut, bestehend aus 5 32Bit-Variablen, die 
jeweils für eine Bitposition stehen. Hierdurch entsteht ein separater 
Counter für jede Bitposition. Das ganze ist vorstellbar als 32 Werte mit 
jeweils 5 Bit, nur "transponiert" (so ähnlich wie in der 
Taster-Entprellroutine von Peter Dannegger: Entprellung).

Angenommen ich habe also für jede Bitposition einen anderen Counterwert, 
wie kann ich parallel für alle Bitpositionen die Counterwerte auf einen 
Bestimmten Bereich prüfen? Also x < Counter < y ist okay, deshalb Flag 
setzen in einer anderen Variable, ansonsten das Flag löschen. Nur eben 
parallel für alle Counter/Bitpositionen.

Ich habe es zuerst mit Boolescher Algebra versucht, die alle Bits auf 
geeignete Weise verUNDet und verODERt, das hat auch gut funktioniert, 
nur leider ist diese Variante sehr statisch hinsichtlich des Bereichs. 
Diesen würde ich gern über Defines festlegen, sodass er variabel bleibt.



Ich hoffe, das war jetzt nicht zu kompliziert, vielen Dank im Voraus!


Viele Grüße,
Christoph

[Steffen R. (steffen_rose)]

Sind es jetzt 5 counter zu je 32Bit oder 32 Counter zu je 5Bit?
Wenn letzteres, warum nutzt du dafür nicht auch 32 Variable?

Dein funktionierender, aber unflexibler Algorithmus würde sicher für das 
Verständnis sinnvoll sein. Auch das Ziel, welches Du erreichen willst, 
wäre nicht schlecht.

Ansonsten:
Betrachte jedes Bit für sich und baue Deine Makros zum Ändern und 
vergleichen getrennt für jedes Bit.

[Stefan W. (dl6dx)]

Christoph B. schrieb:
> Angenommen ich habe also für jede Bitposition einen anderen Counterwert,
> wie kann ich parallel für alle Bitpositionen die Counterwerte auf einen
> Bestimmten Bereich prüfen? Also x < Counter < y

> Ich habe es zuerst mit Boolescher Algebra versucht, die alle Bits auf
> geeignete Weise verUNDet und verODERt, das hat auch gut funktioniert,
> nur leider ist diese Variante sehr statisch hinsichtlich des Bereichs.

Ungeprüfte Idee für einen Ansatz:
Vergleiche deine Zähler (ich nehme an, sie sind als Array uint32_t[5] 
organisiert) mit einem zweiten Array gleicher Struktur, das jeweils den 
Vergleichswert enthält. Für den Vergleich müsstest du einen "vertikalen 
Addierer" bauen, der für das Ergebnis einen Satz Flags (Zero, Negativ, 
etc) bereitstellt. Den Vergleichswert erzeugst du jeweils über eine 
geeignete Funktion. Das könnte dann so aussehen:

typedef uint32_t[5] carr_data_t;
typedef uint32_t[2] carr_flags_t;

carr_data_t counter;
carr_data_t compare;
carr_flags_t flags;

void carr_set(carr_data_t carr, uint8_t wert);

void carr_cmp(carr_data_t carra, carrb);

void main(void)
{
carr_set(counter, 5);
carr_set(compare, 7);

carr_cmp(counter, compare, flags);

/* Flags enthält jetzt das Ergebnis für jeden Zähler */

Die Alternative, die Matrix erst zu transponieren und dann 32 Vergleiche 
zu machen, dürfte wesentlich aufwendiger sein.

Grüße

Stefan

[Yalu X. (yalu) (Moderator)]

Stefan Wagner schrieb:
> Vergleiche deine Zähler (ich nehme an, sie sind als Array uint32_t[5]
> organisiert) mit einem zweiten Array gleicher Struktur, das jeweils den
> Vergleichswert enthält.

Ja, genau so.

Ich habe das hier mal als C-Programm umgesetzt. Die Funktion
lessorequal macht den eignetlichen Vergleich:

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>

void transpose(uint32_t in[], int nin, uint32_t out[], int nout) {
  uint32_t elemin, mask;
  int i, j;

  memset(out, 0, nout * sizeof (uint32_t));
  mask = 1;
  for(i=0; i<nin; i++) {
    elemin = in[i];
    for(j=0; j<nout; j++) {
      if(elemin & 1)
        out[j] |= mask;
      elemin >>= 1;
    }
    mask <<= 1;
  }
}

uint32_t lessorequal(uint32_t a[], uint32_t b[], int n) {
  uint32_t y;
  int i;

  y = ~0;
  for(i=0; i<n; i++)
    y = ~a[i] & (b[i] | y) | b[i] & y;
  return y;
}

void show(uint32_t arr[], int n) {
  int i;

  for(i=0; i<n; i++)
    printf("%2d: %10"PRIu32"\n", i, arr[i]);
}

uint32_t inrange(uint32_t tvalue[], uint32_t tlower[], uint32_t tupper[], int nbits) {
  return lessorequal(tlower, tvalue, nbits) & lessorequal(tvalue, tupper, nbits);
}

#define NVALUES 32
#define NBITS  5

// 32 Zählerwerte à 5 Bit
uint32_t value[NVALUES] = {
   0,  1,  2,  3,  4,  5,  6,  7,
   8,  9, 10, 11, 12, 13, 14, 15,
  16, 17, 18, 19, 20, 21, 22, 23,
  24, 25, 26, 27, 28, 29, 30, 31
};

// 32 Untere Grenzen
uint32_t lower[NVALUES] = {
   8,  8,  8,  8,  9,  9,  9,  9,
  10, 10, 10, 10, 11, 11, 11, 11,
  12, 12, 12, 12, 13, 13, 13, 13,
  14, 14, 14, 14, 15, 15, 15, 15
};

// 32 Obere Grenzen
uint32_t upper[NVALUES] = {
  16, 16, 16, 16, 17, 17, 17, 17,
  18, 18, 18, 18, 19, 19, 19, 19,
  20, 20, 20, 20, 21, 21, 21, 21,
  22, 22, 22, 22, 23, 23, 23, 23
};

uint32_t tvalue[NBITS];
uint32_t tlower[NBITS];
uint32_t tupper[NBITS];

int main(void) {
  uint32_t y;

  // Zählerwerte und Grenzen in vertikale Darstellung transponieren
  transpose(value, NVALUES, tvalue, NBITS);
  transpose(lower, NVALUES, tlower, NBITS);
  transpose(upper, NVALUES, tupper, NBITS);

  // Prüfen, welche der 32 Zählerwerte im erlaubten Bereich liegen
  y = inrange(tvalue, tlower, tupper, NBITS);

  // Bit i von y ist 1 gdw lower[i] <= value[i] <= upper[i]
  printf("%08"PRIx32"\n", y);

  return 0;
}

[Noch einer (Gast)]

Oder einfach so eine Art binäre Suche?

5. Bit gesetzt ?
Ja
  Vergleichswert > 16 ?
    Nein -> fertig, true
    Ja
      4. Bit gesetzt?
      Ja
        Vergleichswert > 20 ?
        Nein -> fertig, true
        ...
Nein
  Vergleichswert >= 16 ?
    Ja -> fertig, false
    ...

Sind ja nur 32 Varianten

[Steffen R. (steffen_rose)]

Stefan Wagner schrieb:
> Vergleiche deine Zähler (ich nehme an, sie sind als Array uint32_t[5]
> organisiert) mit einem zweiten Array gleicher Struktur, das jeweils den
> Vergleichswert enthält.

Die eigentliche Frage war doch nach einer flexiblen Lösung, die er per 
Makro variieren kann. Die gezeigten Lösungen sind effektiv. Aber aus 
meiner Sicht wurde nicht gezeigt, wie man daraus flexible Makros macht.

Ich habe die Flexibilität so verstanden, dass er außer den Zählerwerten, 
welche zu einem Bitwechsel führen, auch die Anzahl der Counterbits je 
bit und global auch die Anzahl der Counter variieren will.

Christoph B. schrieb:
> Ich habe es zuerst mit Boolescher Algebra versucht, die alle Bits auf
> geeignete Weise verUNDet und verODERt, das hat auch gut funktioniert,

@Stefan
Ich gehe mal davon aus, dass er mit seiner Aussage eine Lösung hat, die 
deinem Vorschlag nahe kommt.

Oder habe ich ihn falsch verstanden?

Edit:

Yalu X. schrieb:
> Ich habe das hier mal als C-Programm umgesetzt. Die Funktion
> lessorequal macht den eignetlichen Vergleich:

Die Vergleichs-Tabellen anfangs zu berechnen hatte ich bei dem Vorschlag 
von Stefan übersehen.

[Christoph B. (nuke)]

Yalu X. schrieb:

uint32_t lessorequal(uint32_t a[], uint32_t b[], int n) {
  uint32_t y;
  int i;

  y = ~0;
  for(i=0; i<n; i++)
    y = ~a[i] & (b[i] | y) | b[i] & y;
  return y;
}

Das klingt interessant, an so eine Art und Weise hatte ich gedacht. 
Hättest du auch noch eine kleine Erklärung zu den Bitoperationen, bzw. 
eine Quelle? Konnte leider im Netz auf Anhieb nix finden...

[Possetitjel (Gast)]

Christoph B. schrieb:

> Angenommen ich habe also für jede Bitposition einen
> anderen Counterwert, wie kann ich parallel für alle
> Bitpositionen die Counterwerte auf einen Bestimmten
> Bereich prüfen?

Rückfrage: Der Bereich soll für alle Counter identisch
sein?

Nach meinem laienhaften Verständnis hat Yalu den allgemeinen
Fall mit unterschiedlichen Intervallen je Counter bearbeitet.
Das könnte man evtl. noch vereinfachen.

[Possetitjel (Gast)]

Stefan Wagner schrieb:

> Vergleiche deine Zähler [...] mit einem zweiten Array
> gleicher Struktur, das jeweils den Vergleichswert enthält.

Cool.

Ich hätte gedacht "Das geht nicht!", aber es geht offenbar
doch. Respekt.

[Yalu X. (yalu) (Moderator)]

Es ist a<b genau dann, wenn bei der binären Subtraktion a-b ein Übertrag
(Borgen) entsteht (auf diese Weise funktioniert auch der CMP-Befehl der
meisten Prozessoren).

Die Wahrheitstabelle für den Übertrag c_i+1 bei der Subtraktion der
i-ten Binärstelle in Abhängigkeit von den Binärziffern a_i und b_i und
dem alten Übertrag c_i lautet:

a_i  b_i  c_i | c_i+1    (c_i+1 = 1  <=>  a_i - b_i - c_i < 0)
—————————————————————
 0    0    0  |   0
 0    0    1  |   1
 0    1    0  |   1
 0    1    1  |   1
 1    0    0  |   0
 1    0    1  |   0
 1    1    0  |   0
 1    1    1  |   1
—————————————————————

Dieser logische Zusammenhang wird – beginnend mit der niederwertigsten
Stelle – nacheinander auf die 5 Ziffern der Zahlen angewandt (i=0..4).
Der initiale Übertrag c_0 wird dabei auf 0 gesetzt. Der als letztes
berechnete Übertrag c_5 ist das gesuchte Ergebnis.

Man könnte damit die Bereichsprüfung als Ungleichung u<x<o realisieren.
Will man aber für x den kompletten Wertebereich von 0 bis 31 zulassen,
müsste die untere Grenze u=-1 und die obere o=32 sein. Beide Werte sind
aber mit 5 Bits nicht darstellbar.

Dieses Problem umgeht man, indem man stattdessen die Ungleichung u≤x≤o
verwendet. Dazu braucht man die Relation a≤b. Diese erhält man dadurch,
dass man in a<b die Operanden vertauscht (b<a bzw. a>b) und das Ergebnis
negiert (a≯b bzw. a≤b). Die negierten Überträge seien y genannt (y=¬c).
Die entsprechende Wahrheitstabelle lässt sich damit auf einfache Weise
aus der obigen für a<b ableiten:

b_i  a_i  y_i | y_i+1
—————————————————————
 0    0    1  |   1
 0    0    0  |   0
 0    1    1  |   0
 0    1    0  |   0
 1    0    1  |   1
 1    0    0  |   1
 1    1    1  |   1
 1    1    0  |   0
—————————————————————

Durch scharfes Hinsehen oder Verwendung eines KV-Diagramms ergibt sich
daraus der logische Term

  yi'  =  ¬ai ∧ bi  ∨  ¬ai ∧ yi  ∨  bi ∧ yi
       =  ¬ai ∧ (bi ∨ yi)  ∨  bi ∧ yi

Das ist genau der Term, welcher in der Funktion lessorequal verwendet
wird. Da c den Initialwert 0 hat, muss y wegen y=¬c entsprechend mit ¬0
starten.

[Christoph B. (nuke)]

Sehr schöne Erklärung, vielen Dank! Da wäre ich ohne Weiteres nicht 
drauf gekommen ;-)