Extrahier n Bits über mehrere Bytes von einer Startposition aus, rechtsbündig

Bartosz · 1. Oktober 2024, 19:37

Hallo zusammen,

ich habe folgendes Problem:
Ich habe ein Byte-Array und ich möchte eine bestimmte Anzahl von Bits aus diesem Array ab einer bestimmten Startposition extrahieren und als Dezimalzahl zurückbekommen. Die Herausforderung besteht darin, Bits über mehrere Bytes hinweg zu lesen.
Beispiel:
Byte 1 ist 003 (00000011 in binär).
Byte 2 ist 148 (10010100 in binär).
Ich möchte ab der 8. Position (letztes Bit des ersten Bytes) lesen, und zwar die nächsten 6 Bits.

Quellcode

Friend Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), startPosition As Integer, bitCount As Integer) As UInteger
{3, 148} 7 6

Das heißt, ich erwarte als Ergebnis die Zahl 50, denn:
00000011 10010100
0000000 x xxxxx lies das als 110010. Das sind in Dezimalschreibweise 50. (Wobei hier gedanklich 2 führende Nullen voranstehen, also 00110010).

Ich bin in sowas leider nicht gut und ich schätze eure Hilfe.
Viele Grüße
Bartosz

VaporiZed · 1. Oktober 2024, 22:04

Pfeil-Rücken-Brust-Auge: per Strings.
mathematisch:
zwei Bytes hintereinander = Byte1 x 256 +Byte2 = Zahl3 (00000011 10010100 alias 916)
Dann willst Du nur bestimmte Stellen. Das machst Du mit ner Bitmaske und AND. Wenn Du also das Ergebnis (Zahl3) AND 111111000 nimmst, werden nur die Einsen bleiben, die in der Bitmaske und auch in Zahl3 binär eine 1 waren.
111111000 = Binärdarstellung für die Zahl 504.
Am Ende verschiebst Du das Ergebnis noch und fertig.
Also:

VB.NET-Quellcode

DeinErgebnis = ((Byte1 * 256 + Byte2) And 504) >> 3

DTF · 1. Oktober 2024, 22:43

Ich denke du hast schon einen Denkfahler drin.

Das byteArray index 0 = 3 und index 1 = 148 ergibt binär 1001010000000011, probiers mal aus:

C#-Quellcode

Byte[] bytes = new byte[] { 148 , 3 };
BigInteger big = new BigInteger(bytes, true);
Console.WriteLine(big.ToString("B16"));

Also um auf die 50 zu kommen, dreh ich das Byte[] einmal um:(bedenke das auch BitInteger ein limit hat)
Wenn du dir das so mal ausgeben lässt, ist das doch einfach zu verstehen

C#-Quellcode

using System.Numerics;
namespace ConsoleApp1
{
internal class Program
{
static void Main(string[] args)
{
Byte[] bytes = new byte[] { 3, 148 }.Reverse().ToArray();
BigInteger big = new BigInteger(bytes, true);
Console.WriteLine(big.ToString("B16"));
int bitCount = 6;
int startBit = 7;
BigInteger mask = (1 << bitCount) - 1;
int toShift = ((bytes.Length * 8) - startBit - bitCount);
mask = mask << toShift;
Console.WriteLine(mask.ToString("B16"));
BigInteger result = big & mask;
Console.WriteLine(result.ToString("B16"));
Console.WriteLine((result >> toShift).ToString("B16"));
Console.WriteLine(result >> toShift);
Console.ReadKey();
}
}
}

Haudruferzappeltnoch · 1. Oktober 2024, 22:57

So täte ich

VB.NET-Quellcode

Public Function SubUInt(input As Byte(), start As Integer, length As Integer) As UInteger
If length > 32 Then Throw New ArgumentException("length is too big. No more than 32 bits fit into UInt")
Dim remStart, remEnd As Integer
Dim startIndex = Math.DivRem(start - 1, 8, remStart)
Dim endIndex = Math.DivRem(start + length - 1, 8, remEnd)
Dim result As UInteger = input(startIndex) << remStart >> remStart
For i = startIndex + 1 To endIndex - 1
result = (result << 8) Or input(i)
Next
Return (result << remEnd) Or (input(endIndex) >> (8 - remEnd))
End Function

Edit: Siehe weiter unten für Verbesserung

RodFromGermany · 2. Oktober 2024, 09:06

Haudruferzappeltnoch schrieb:

VB.NET-Quellcode

Dim result As UInteger = input(startIndex) << remStart >> remStart

Mach da mal Klammern rein, sonst kommt da ggf. was falsches raus.

Haudruferzappeltnoch · 2. Oktober 2024, 09:52

Die Berechnung ist kein Zufall: Entweder es kommt was Falsches raus oder es kommt nix Falsches raus. Die Klammern helfen höchstens beim Verständnis
In diesem Fall kommt nix Falsches raus. << und >> haben denselben Rang.

exc-jdbi · 2. Oktober 2024, 12:33

Kurz über Mittag geschrieben.

Wenn alles stimmt, sollte es so funktionieren. Ist jedoch 0-Basierend.

Freundliche Grüsse

exc-jdbi

EDIT: Extentions hinzugefügt. Ungetestet. Viel Spass.

C#-Quellcode

[/b]var ul = 123456789ul;

//BitConverter konvertiert alles immer LittleEndien.

var bytes = BitConverter.GetBytes(ul);

var isbigendian = false;

var start = 7;

var length = 8;

var bits_ul= new ReadOnlySpan<byte>(bytes).SubBitsUI64(start, length, isbigendian);

var bits_str = new ReadOnlySpan<byte>(bytes).SubBitsString(start, length, isbigendian);

var bits_ul2 = Convert.ToUInt64(bits_str, 2);

var bits_bytes = new ReadOnlySpan<byte>(bytes).SubBitsBytes(start, length, isbigendian);

var bits_bi2 = new BigInteger(bits_bytes, true, isbigendian);

var bits_bi = new ReadOnlySpan<byte>(bytes).SubBitsBigInteger(start, length, isbigendian);[b]

C#

C#-Quellcode

using System.Text;
namespace ReadBitsFromMultiBytes;
public class Program
{
public static void Main()
{
Test();
Console.WriteLine();
Console.WriteLine("FINISH");
Console.WriteLine();
Console.ReadLine();
}
public static void Test()
{
//var bytes = new byte[] { 3, 148 };
for (var i = 0; i < 10000; i++)
{
var rand = Random.Shared;
var count = rand.Next(2, 9); // 8 = ulong-bytes
var bitlen = 8 * count;
var start = 0;
var length = int.MaxValue;
while (start + length >= bitlen)
{
start = rand.Next(bitlen / 4, bitlen / 2);
length = rand.Next(2, bitlen - start);
}
var bytes = RngBytes(count);
var ul1 = Example1(bytes, start, length);
var ul2 = Example2(bytes, start, length);
if (ul1 != ul2) throw new Exception();
}
}
private static ulong Example1(
ReadOnlySpan<byte> bytes, int start, int length)
{
var ulong_number = ToUlong(bytes, start, length);
//Console.WriteLine(ulong_number);
return ulong_number;
}
private static ulong Example2(
ReadOnlySpan<byte> bytes, int start, int length)
{
var ulong_number = ToUlongBytes(bytes, start, length);
//Console.WriteLine(ulong_number);
return ulong_number;
}
private static ulong ToUlong(
ReadOnlySpan<byte> bits, int start, int length) =>
length > 0 && length <= 64
? Convert.ToUInt64(ToBitsString(bits, start, length), 2)
: 0;
private static string ToBitsString(
ReadOnlySpan<byte> bits, int start, int length)
{
var result = new StringBuilder();
foreach (var bit in bits)
result.Append(Convert.ToString(bit, 2).PadLeft(8, '0'));
//Console.WriteLine(result.ToString());
return result.ToString().Substring(start, length);
}
private static byte[] ToBytes(string bits) =>
Enumerable.Range(0, bits.Length / 8).
Select(x => Convert.ToByte(bits.Substring(x * 8, 8), 2)).ToArray();
private static ulong ToUlongBytes(
ReadOnlySpan<byte> bytes, int start, int length)
{
ulong result = 0;
for (var i = 0; i < bytes.Length; i++)
result |= Convert.ToUInt64(bytes[^(i + 1)]) << (i * 8);
//pos von rechts gesehen
var real_start = bytes.Length * 8 - start - length;
result >>= real_start;
result <<= 64 - length;
result >>= 64 - length;
return result;
}
private static byte[] RngBytes(int size)
{
var bytes = new byte[size];
Random.Shared.NextBytes(bytes);
return bytes;
}
}

Vb.Net

VB.NET-Quellcode

Option Strict On
Option Explicit On
Imports System.Text
Namespace ReadBitsFromMultiBytes
Public Class Program
Public Shared Sub Main()
Test()
Console.WriteLine()
Console.WriteLine("FINISH")
Console.WriteLine()
Console.ReadLine()
End Sub
Public Shared Sub Test()
For i = 0 To 10000 - 1
Dim rand = Random.[Shared]
Dim count = rand.[Next](2, 9)
Dim bitlen = 8 * count
Dim start = 0
Dim length = Integer.MaxValue
While start + length >= bitlen
start = rand.[Next](bitlen \ 4, bitlen \ 2)
length = rand.[Next](2, bitlen - start)
End While
Dim bytes = RngBytes(count)
Dim ul1 = Example1(bytes, start, length)
Dim ul2 = Example2(bytes, start, length)
If ul1 <> ul2 Then Throw New Exception()
Next
End Sub
Private Shared Function Example1(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
Dim ulong_number = ToUlong(bytes, start, length)
Return ulong_number
End Function
Private Shared Function Example2(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
Dim ulong_number = ToUlongBytes(bytes, start, length)
Return ulong_number
End Function
Private Shared Function ToUlong(bits As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
Return If(length > 0 AndAlso length <= 64, Convert.ToUInt64(ToBitsString(bits, start, length), 2), 0UL)
End Function
Private Shared Function ToBitsString(bits As IEnumerable(Of Byte), start As Integer, length As Integer) As String
Dim result = New StringBuilder()
For Each bit In bits
result.Append(Convert.ToString(bit, 2).PadLeft(8, "0"c))
Next
Return result.ToString().Substring(start, length)
End Function
Private Shared Function ToBytes(bits As String) As Byte()
Return Enumerable.Range(0, bits.Length \ 8).[Select](Function(x) Convert.ToByte(bits.Substring(x * 8, 8), 2)).ToArray()
End Function
Private Shared Function ToUlongBytes(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
Dim result = 0UL
For i = 0 To bytes.Count - 1
result = result Or Convert.ToUInt64(bytes(bytes.Count - i - 1)) << (i * 8)
Next
Dim real_start = bytes.Count * 8 - start - length
result = result >> real_start
result = result << (64 - length)
result = result >> (64 - length)
Return result
End Function
Private Shared Function RngBytes(size As Integer) As Byte()
Dim bytes = New Byte(size - 1) {}
Random.Shared.NextBytes(bytes)
Return bytes
End Function
End Class
End Namespace

DTF · 2. Oktober 2024, 14:28

DTF schrieb:

(bedenke das auch BitInteger ein limit hat)

Ich hab mal geschaut wo da die Grenzen sind, BigInteger ist kein Problem, wird kein Problem mit zu vielen Bytes geben, weil das Maximum ist das:
Byte[] bytes = new byte[2147483591];
Nur ein Byte mehr und es gibt eine Fehlermeldung:
System.OutOfMemoryException: "Array dimensions exceeded supported range."

Von daher kann man mein Beispiel anwenden, ohne Angst zu haben das man das Maximum eines BitInteger überschreitet.

Bartosz · 2. Oktober 2024, 17:42

@Haudruferzappeltnoch Da stimmt noch was nicht. Ich erhalte bei den Vorgaben {3, 148}, startPosition = 7 und bitCount=6, nicht 50, sondern 53.
@DTF Danke, das funktioniert. Gibt es eine Lösung, bei der man das Byte-Array nicht reversen muss? Es könnte unter Umständen als sehr großes Byte-Array reinkommen.

Viele Grüße
Bartosz

Haudruferzappeltnoch · 2. Oktober 2024, 17:47

Wie rufst du die Methode auf?

VB.NET-Quellcode

Dim a as Byte() = {3, 148}
Dim b = SubUInt(a, 8, 6)

Ist bei mir 50

Achso ja start ist bei mir versetzt. 8 statt 7

exc-jdbi · 2. Oktober 2024, 18:03

Bartosz schrieb:

Byte-Array nicht reversen

Ja die gibt es.

C#-Quellcode

var result = new BigInteger(bytes, true, true);

In VB.Net ist es genau gleich.

Ansonsten so machen wie ich es gemacht habe, in dem das Byte-Array von hinten aufgezogen wird.

Freundliche Grüsse

exc-jdbi

wolfi_bayern · 2. Oktober 2024, 19:29

evtl ist bitarray ein passendes Werkzeug:

learn.microsoft.com/en-us/dotn…t-8.0&redirectedfrom=MSDN

DTF · 2. Oktober 2024, 19:33

@exc-jdbi
Jupp, diesen Kostruktor hatte ich nicht mehr im Sinn. BigInteger hat MS aber auch nicht ausführlich dokumentiert, nicht mal alle Konstruktoren sind hier gelistet. Wobei ich bei ReadOnlySpan die implizite Konvertierung von Byte[] -> ReadOnlySpan<Byte> nicht gesehen hab.
learn.microsoft.com/en-us/dotn…s.biginteger?view=net-8.0

Auch eine Range kann ich nicht finden, da steht nur "eine willkürlich große Zahl".

Bartosz · 2. Oktober 2024, 22:33

Ein großes Dankeschön!
Ich habe es nun gelöst bekommen. Ich nutze DTFs Vorschlag (Haudruferzappeltnochs Vorschlag probiere ich morgen nach dem Schlafen nochmal in Ruhe aus). Allerdings ohne Big Integer zu nutzen. Ich nutze stattdessen eine For-Schleife, um die Zahl, die bei DTF 'big' heißt, zu bekommen. Das ist ja im Grunde genommen nur
{3, 148} ->

$ 148 \cdot 256^{0} + 3 \cdot 256^{1} = 916 $

. Das Problem ist nämlich auch, dass das Byte-Array 4 Bytes groß in die Funktion reinkommen könnte. Es besteht nicht immer aus 2 Bytes. Vielleicht kann jemand die For-Schleife noch verbessern?

VB.NET-Quellcode

''' <summary>
''' <code>
''' 003 = 0000 0011
''' 148 = 1001 0100
''' Startposition (als Index) sei = 7 und bitCount sei = 6
''' 00000011 10010100
''' -------x xxxxx---
''' Ergibt (00)110010 = 50
''' </code>
''' </summary>
''' <param name="bytes"></param>
''' <param name="bitStartPositionAsIndex"></param>
''' <param name="bitCount"></param>
''' <returns></returns>
Friend Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), bitStartPositionAsIndex As Integer, bitCount As Integer) As UInteger
'bytes = New Byte() {3, 148}
'bytes = New Byte() {5}
'bitCount = 3
'bitStartPositionAsIndex = 5
If bitStartPositionAsIndex >= bytes.Length * 8 Then
Throw New ArgumentException($"{NameOf(bitStartPositionAsIndex)} is too large ({bitStartPositionAsIndex}) for the byte array with a size of {bytes.Length}.")
End If
' I want to use a loop to iterate backward from a specified start byte position to the end byte position,
' multiplying each byte by the corresponding power of 256.
Dim big As UInt32 = 0UI
Dim byteCount As Integer = CInt(Math.Ceiling(bitCount / 8.0))
Dim byteStart As Integer = bitStartPositionAsIndex \ 8
Dim cnt As Integer = 0
Dim loopStart As Integer = Math.Min(byteCount + byteStart, bytes.Length - 1)
For i As Integer = loopStart To byteStart Step -1
big += bytes(i) * CUInt(Math.Pow(256, cnt))
cnt += 1
Next
'----------------
Dim mask As Integer = (1 << bitCount) - 1
Dim toShift As Integer = ((bytes.Length * 8) - bitStartPositionAsIndex - bitCount)
mask = mask << toShift
Dim result As UInt32 = CUInt(big And mask)
#If DEBUG Then
Debug.WriteLine($"ExtractBitsAcrossBytesFromPositionRightAligned: {result >> toShift}")
#End If
Return result >> toShift
End Function

Bartosz · 3. Oktober 2024, 09:44

@'Haudruferzappeltnoch'
Achso ja start ist bei mir versetzt. 8 statt 7
Ok, danke. So komme ich auch auf die 50. Da war ich wohl gestern zu kaputt.

Bartosz · 3. Oktober 2024, 12:14

Ich muss mich leider noch einmal melden. Die Funktion nutzt die gesamte Länge des Byte-Arrays: Dim toShift As Integer = ((bytes.Length * 8) - bitStartPositionAsIndex - bitCount). Das ist nicht gut. Wenn es z.B. 27 Bytes groß ist, wird das Ergebnis anders. Kann man das verbessern? Angenommen, StartPosition ist 27, also mitten im Byte mit dem Index 3, und wir wollen 2 Bit lesen. Das Ergebnis ist anders, als wenn ein Byte-Array mit einem Byte reinkommt und man ab entsprechender Stelle (3) liest.

Haudruferzappeltnoch · 3. Oktober 2024, 18:01

Wenn ich 2 Bit lese sollte das Ergebnis doch auch anders sein als wenn ich 3 Bit lese, oder?
Gib deinen Testcase an, ich habe nicht viel rumprobiert.
Da sind sicher paar Unstimmigkeiten drin, aber du kannst ja auch mal selbst versuchen das auszubauen, einige Ideen findest du in jedem Codebeispiel, das hier dargestellt wurde.

Bartosz · 3. Oktober 2024, 18:24

@Haudruferzappeltnoch
Ich stelle gerne zwei konkrete Beispiele zur Verfügung:
Beispiel 1:
{103, 100, 0, 51, 172}
bitStartPositionAsIndex = 27 (mitten im Byte mit dem Wert 51 → 00110011)
bitCount = 2
Funktion gibt 0 zurück.

Beispiel 2:
{51}
bitStartPositionAsIndex = 3 (dieselbe Position 00110011)
bitCount = 2
Funktion gibt 2 zurück.

Spoiler anzeigen

VB.NET-Quellcode

''' <summary>
''' <code>
''' Byte-Array {3, 148}
''' 003 = 0000 0011
''' 148 = 1001 0100
''' Startposition (als Index) sei = 7 und bitCount sei = 6
''' 00000011 10010100
''' -------x xxxxx---
''' Ergibt (00)110010 = 50
''' </code>
''' </summary>
''' <param name="bytes"></param>
''' <param name="bitStartPositionAsIndex"></param>
''' <param name="bitCount"></param>
''' <returns></returns>
Private Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), bitStartPositionAsIndex As Integer, bitCount As Integer) As UInteger
If bitStartPositionAsIndex >= bytes.Length * 8 Then
Throw New ArgumentException($"{NameOf(bitStartPositionAsIndex)} is too large ({bitStartPositionAsIndex}) for the byte array with a size of {bytes.Length} bytes.")
End If
' I want to use a loop to iterate backward from a specified start byte position to the end byte position,
' multiplying each byte by the corresponding power of 256.
Dim big As UInt32 = 0UI
Dim byteCount As Integer = CInt(Math.Ceiling(bitCount / 8.0))
Dim byteStart As Integer = bitStartPositionAsIndex \ 8
Dim cnt As Integer = 0
Dim loopStart As Integer = Math.Min(byteCount + byteStart, bytes.Length - 1)
For i As Integer = loopStart To byteStart Step -1
big += bytes(i) * CUInt(Math.Pow(256, cnt))
cnt += 1
Next
'----------------
Dim mask As Integer = (1 << bitCount) - 1
Dim toShift As Integer = ((bytes.Length * 8) - bitStartPositionAsIndex - bitCount)
mask = mask << toShift
Dim result As UInt32 = CUInt(big And mask)
#If DEBUG Then
Debug.WriteLine($"ExtractBitsAcrossBytesFromPositionRightAligned: {result >> toShift}")
#End If
Return result >> toShift
End Function

Haudruferzappeltnoch · 3. Oktober 2024, 19:45

Du benutzt zwar nicht meine obige Funktion, aber die kann man sowieso in die Tonne schmeißen. Da waren viele Sachen unberücksichtigt.

Das ist jetzt null-basiert und einfacher durchzublicken. Das Hauptproblem war das Binäroperationen mit Byte keine gute Idee sind, wenn man UInt am Ende rauskriegen will. Verhält sich jetzt deutlich ähnlicher zu Substring

VB.NET-Quellcode

Public Shared Function SubUInt(input As Byte(), start As Integer, length As Integer) As UInteger
If length > 32 Then Throw New ArgumentException("length is too big. No more than 32 bits fit into UInt")
If start < 0 OrElse start + length > 8 * input.Length Then Throw New ArgumentOutOfRangeException("start or end not inside array bounds")
If length = 0 Then Return 0
Dim startIndex = start \ 8
Dim endIndex = (start + length - 1) \ 8
Dim remE = (start + length) Mod 8
Dim a = input.Skip(startIndex).Take(1 + endIndex - startIndex).Select(AddressOf Convert.ToUInt32).Aggregate(Function(x, y) x << 8 Or y)
Return a >> ((8 - remE) Mod 8) And (CUInt(1) << length) - 1
End Function

Extrahier n Bits über mehrere Bytes von einer Startposition aus, rechtsbündig

Extrahier n Bits über mehrere Bytes von einer Startposition aus, rechtsbündig

Quellcode

VB.NET-Quellcode

C#-Quellcode

C#-Quellcode

VB.NET-Quellcode

Haudruferzappeltnoch schrieb:

VB.NET-Quellcode

C#-Quellcode

C#-Quellcode

VB.NET-Quellcode

DTF schrieb:

VB.NET-Quellcode

Bartosz schrieb:

C#-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

Benutzer online 2

Ähnliche Themen

7 Benutzer haben hier geschrieben