DoubleDabble in Java
Ich wollte als Fingerübung wieder einmal einen Algorithmus umsetzen - dieses Mal doubledabble zum Encoding und Decoding von packed binary-coded decimal (BCD) Zahlen. Ich stellte zu meinem Erstaunen fest, dass das nicht einfach ist...
Der Algorithmus erfordert ein Bitfeld variabler - aber fester - Länge, die nicht notwendigerweise ein Vielfaches von 8 ist.
Ich suchte lange, fand aber keine Datenstruktur (Datentyp, Klasse - der Name ist egal), die diese Anforderungen erfüllte. Die Klasse BitSet ist leider genau das: ein Set, das keine Größenbeschränkung aufweist.
Mit den Klassen Long und Byte ist einem hier auch nicht geholfen, da diese die Einschränkung jhaben, dass die Anzahl der Bits hierin (oder in Arrays daraus) immer ein Vielfaches von 8 sind. Auch BigInteger ist keine Hilfe - Auch dieser Typ hat keine Beschränkung seiner Größe - er wächst bei Bedarf einfach mit...
Hmmm - habe ich hier wirklich eine Facette gefunden, die noch ungelöst ist? Und sollte man eine Klasse (einen Typ) implementieren, der das gewünschte Verhalten abbildet?
Tests sollten einfach sein: Die Klasse leitet man von Number ab und schreibt zunächst jede Menge Tests, die alle arithmetischen Funktionen in den ebenfalls davon abgeleiteten Ordinaltypen mit entsprechenden Sonderfällen prüfen und sicherstellen, dass das Verhalten der neuen Klasse mit den jeweils passenden Bitlängen identisch ist. Anschließend gilt es noch entsprechende Tests für Bitlängen, die keine Vielfachen von 8 sind zu schreiben und deren Korrektheit zu validieren.
Ich habe mich letztlich dagegen entschieden, diesen Aufwand zu betreiben - statt dessen habe ich eine Klasse geschrieben, die die 5 gewünschten Operationen
- shl - Shift Left,
- shr - Shift Right,
- sshl - Signed Shift Left
- rol - Rotate Left
- ror - Rotate Right
Letztlich habe ich mich dazu entschieden, statt dessen ein BitSet zu nutzen und eine Maske dazuzubauen, die aus n Einsen besteht (wobei 'n' die Länge des BitSet sein soll) - dann muss nur noch nach jeder Operation das Ergebnis der Operation logisch UND-verknüpft werden mit dieser Maske. Die Maske kann gebaut werden indem man die Methode set benutzt.
Auch diese Idee wurde letztlich verworfen und ich habe mich entschieden, einfach nach jeder Operation die Methode get zu nutzen, um das Bitset wieder auf die ursprüngliche Länge zu stutzen.
Der eigentliche Grund, von der Idee der Nutzung der eingebauten Typen abzuweichen war die zusätzliche Schwierigkeit, dass das Ergebnis der Methode toByteArray der Klasse BigInteger genau anders herum zählt als das BitSet: Man kann einen BigInteger und ein BitSet nicht einfach über deren jeweilige Byte-Array Representation ineinander umwandeln: Der Wert 65531 ergibt als Byte-Array aus BigInteger heraus eines, dessen 0-tes Byte den Wert 0 und dessen zweites den Wert -1 hat - die Methode toString eines daraus erzeugten BitSet allerdings liefert als Indices {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23} und nicht das (von mir) erwartete Resultat {0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
Der aktuelle Stand der Implementation zeigt eine Konvertierungsmethode:
public class FixedLengthBitSet extends java.lang.Object implements java.lang.Cloneable
{
private final int length;
private java.util.BitSet value;
private boolean carry;
public FixedLengthBitSet(int length)
{
this((java.util.BitSet)null,length);
}
public FixedLengthBitSet(java.lang.Number n,int length)
{
this(java.math.BigInteger.valueOf(n.longValue()),length);
}
public FixedLengthBitSet(java.math.BigInteger bi,int length)
{
this(valueOf(bi,length),length);
}
public FixedLengthBitSet(java.util.BitSet bs,int length)
{
super();
if(length<1)
throw new java.lang.IllegalArgumentException("length must be at least 1!");
this.length=length;
this.value=bs!=null?(java.util.BitSet)bs.clone():new java.util.BitSet();
}
@Override
public Object clone() throws CloneNotSupportedException
{
FixedLengthBitSet clone=(FixedLengthBitSet)super.clone();
clone.value=(java.util.BitSet)value.clone();
return clone;
}
private void clearCarry()
{
carry=false;
}
private void carryLeft()
{
carry=value.get(length-1);
}
private void carryRight()
{
carry=value.get(0);
}
public FixedLengthBitSet ror()
{
clearCarry();
boolean sign=value.get(0);
carryRight();
shr();
if(sign)
value.set(length-1);
return this;
}
public FixedLengthBitSet rol()
{
clearCarry();
boolean sign=value.get(length-1);
carryLeft();
shl();
if(sign)
value.set(0);
return this;
}
public FixedLengthBitSet shr()
{
clearCarry();
carryRight();
value=value.get(1,length);
return this;
}
public FixedLengthBitSet sshr()
{
clearCarry();
boolean sign=value.get(length-1);
carryRight();
shr();
if(sign)
value.set(length-1);
return this;
}
public FixedLengthBitSet shl()
{
return shl(false);
}
public FixedLengthBitSet shl(boolean carry)
{
clearCarry();
java.util.BitSet bs=new java.util.BitSet();
carryLeft();
for(int i=1,j=0;i<length;++i,++j)
{
if(value.get(j))
bs.set(i);
else
bs.clear(i);
}
if(carry==true)
bs.set(0);
value=bs;
return this;
}
private static java.util.BitSet valueOf(java.math.BigInteger bi, int length)
{
java.util.BitSet bs=valueOf(bi);
if(bi.signum()==-1)
{
for(int i=length-1;i>=0;--i)
{
if(bs.get(i)==false)
bs.set(i);
else
break;
}
}
return bs;
}
public static java.util.BitSet valueOf(java.math.BigInteger bi)
{
byte[] bytes=bi.toByteArray();
byte[] reverted=new byte[bytes.length];
for(int i=bytes.length-1;i>=0;--i)
{
reverted[i]=bytes[bytes.length-1-i];
}
java.util.BitSet bs=java.util.BitSet.valueOf(reverted);
return bs;
}
public java.math.BigInteger asTwosComplementBigInteger()
{
java.math.BigInteger rv=java.math.BigInteger.valueOf(0);
for(int i=0;i<length-1;++i)
{
if(value.get(i))
rv=rv.add(java.math.BigInteger.valueOf(1<<i));
}
if(value.get(length-1))
rv=rv.subtract(java.math.BigInteger.valueOf(1<<(length-1)));
return rv;
}
public java.math.BigInteger asBigInteger()
{
java.math.BigInteger rv=java.math.BigInteger.valueOf(0);
for(int i=length-1;i>=0;--i)
{
rv=rv.shiftLeft(1);
if(value.get(i))
rv=rv.or(java.math.BigInteger.valueOf(1));
}
return rv;
}
public int getLength()
{
return length;
}
public java.util.BitSet getValue()
{
return value.get(0,length);
}
public boolean isCarry()
{
return carry;
}
@Override
public java.lang.String toString()
{
return asBigInteger().toString()+" -- "+asTwosComplementBigInteger().toString()+" --" +asBigInteger().toString(16)+" -- "+getValue().toString();
}
}
Und damit lässt sich dann auch der Algorithmus umsetzen:
private static java.util.List<de.elbosso.util.lang.FixedLengthBitSet> doubleDabble(int in)
{
java.math.BigInteger input=java.math.BigInteger.valueOf(in);
int n=input.bitLength();
de.elbosso.util.lang.FixedLengthBitSet original=new de.elbosso.util.lang.FixedLengthBitSet(input,n);
java.util.List<de.elbosso.util.lang.FixedLengthBitSet> nibbles=new java.util.LinkedList<>();
nibbles.add(new de.elbosso.util.lang.FixedLengthBitSet(4));
for(int i=0;i<n;++i)
{
original.shl();
boolean bitSet=original.isCarry();
for(int j=0;j<nibbles.size();++j)
{
if(nibbles.get(j).asBigInteger().intValue()>4)
{
nibbles.set(j,new de.elbosso.util.lang.FixedLengthBitSet(nibbles.get(j).asBigInteger().add(java.math.BigInteger.valueOf(3)),4));
}
nibbles.get(j).shl(bitSet);
bitSet=nibbles.get(j).isCarry();
}
if(bitSet==true)
{
nibbles.add(new de.elbosso.util.lang.FixedLengthBitSet(java.math.BigInteger.valueOf(1),4));
}
}
return nibbles;
}
Vor 5 Jahren hier im Blog
-
The Things (Network) Stack v3
19.09.2021
Ich berichtete vor einiger Zeit über meine ersten Versuche der Beschäftigung mit LoRaWAN und The Things Netzwork.
Weiterlesen
Tags
AI und ML Android Basteln C und C++ Chaos Datenbanken Docker dWb+ ESP Wifi Garten Geo Go GUI Hardware Java Jupyter JupyterBinder Komponenten Links Linux Markdown Markup Music Numerik OpenSource PKI-X.509-CA Präsentationen Python QBrowser Rants Raspi Revisited Security Software-Test sQLshell TeleGrafana Verschiedenes Video Virtualisierung Windows Upcoming...
Neueste Artikel
-
Docker Upgrade Fail 2026
Gerade habe ich Urlaub - und Urlaub bei mir heißt auch immer Maintenance im Heimlabor. Das wiederum heißt Updates und Upgrades für die verschiedenen Server, Dienste und Virtualisierungsplattformen. Und natürlich geht auch immer etwas schief - auch dieses Mal...
Weiterlesen -
Flaggen-Emojis aus ISO3166-1 Country Codes
Ich fand neulich diesen interessanten Link, der beschreibt, wie man die Flaggenicons für alle Länder der Erde mit einem simplen Unicode-Feature erzeugen kann und dachte: "Das will ich auch ausprobieren!". Wieder etwas, das ich noch nicht über Unicode wusste...
Weiterlesen -
Cryptpad neu im Docker Zoo
Ich habe nochmal versucht, Cryptpad als self-hosted Variante in meinen Docker-Zoo aufzunehmen - dieses Mal war ich erfolgreich...
Weiterlesen
Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.
Wer daran teilhaben und eventuell sogar davon profitieren möchte, muss damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.
Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...
PS: Meine öffentlichen Codeberg-Repositories findet man hier.