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

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 18 Antworten in diesem Thema. Der letzte Beitrag () ist von Haudruferzappeltnoch.

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

    Neu

    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

    1. ​ Friend Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), startPosition As Integer, bitCount As Integer) As UInteger
    2. {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

    Neu

    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

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

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

    Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.

    Neu

    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

    1. Byte[] bytes = new byte[] { 148 , 3 };
    2. BigInteger big = new BigInteger(bytes, true);
    3. 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

    1. using System.Numerics;
    2. namespace ConsoleApp1
    3. {
    4. internal class Program
    5. {
    6. static void Main(string[] args)
    7. {
    8. Byte[] bytes = new byte[] { 3, 148 }.Reverse().ToArray();
    9. BigInteger big = new BigInteger(bytes, true);
    10. Console.WriteLine(big.ToString("B16"));
    11. int bitCount = 6;
    12. int startBit = 7;
    13. BigInteger mask = (1 << bitCount) - 1;
    14. int toShift = ((bytes.Length * 8) - startBit - bitCount);
    15. mask = mask << toShift;
    16. Console.WriteLine(mask.ToString("B16"));
    17. BigInteger result = big & mask;
    18. Console.WriteLine(result.ToString("B16"));
    19. Console.WriteLine((result >> toShift).ToString("B16"));
    20. Console.WriteLine(result >> toShift);
    21. Console.ReadKey();
    22. }
    23. }
    24. }

    Zitat von mir 2023:
    Was interessiert mich Rechtschreibung? Der Compiler wird meckern wenn nötig :D

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „DTF“ ()

    Neu

    So täte ich

    VB.NET-Quellcode

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

    Edit: Siehe weiter unten für Verbesserung

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Neu

    Haudruferzappeltnoch schrieb:

    VB.NET-Quellcode

    1. Dim result As UInteger = input(startIndex) << remStart >> remStart
    Mach da mal Klammern rein, sonst kommt da ggf. was falsches raus.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Neu

    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

    1. [/b]var ul = 123456789ul;
    2. //BitConverter konvertiert alles immer LittleEndien.
    3. var bytes = BitConverter.GetBytes(ul);
    4. var isbigendian = false;
    5. var start = 7;
    6. var length = 8;
    7. var bits_ul= new ReadOnlySpan<byte>(bytes).SubBitsUI64(start, length, isbigendian);
    8. var bits_str = new ReadOnlySpan<byte>(bytes).SubBitsString(start, length, isbigendian);
    9. var bits_ul2 = Convert.ToUInt64(bits_str, 2);
    10. var bits_bytes = new ReadOnlySpan<byte>(bytes).SubBitsBytes(start, length, isbigendian);
    11. var bits_bi2 = new BigInteger(bits_bytes, true, isbigendian);
    12. var bits_bi = new ReadOnlySpan<byte>(bytes).SubBitsBigInteger(start, length, isbigendian);[b]



    C#

    C#-Quellcode

    1. using System.Text;
    2. namespace ReadBitsFromMultiBytes;
    3. public class Program
    4. {
    5. public static void Main()
    6. {
    7. Test();
    8. Console.WriteLine();
    9. Console.WriteLine("FINISH");
    10. Console.WriteLine();
    11. Console.ReadLine();
    12. }
    13. public static void Test()
    14. {
    15. //var bytes = new byte[] { 3, 148 };
    16. for (var i = 0; i < 10000; i++)
    17. {
    18. var rand = Random.Shared;
    19. var count = rand.Next(2, 9); // 8 = ulong-bytes
    20. var bitlen = 8 * count;
    21. var start = 0;
    22. var length = int.MaxValue;
    23. while (start + length >= bitlen)
    24. {
    25. start = rand.Next(bitlen / 4, bitlen / 2);
    26. length = rand.Next(2, bitlen - start);
    27. }
    28. var bytes = RngBytes(count);
    29. var ul1 = Example1(bytes, start, length);
    30. var ul2 = Example2(bytes, start, length);
    31. if (ul1 != ul2) throw new Exception();
    32. }
    33. }
    34. private static ulong Example1(
    35. ReadOnlySpan<byte> bytes, int start, int length)
    36. {
    37. var ulong_number = ToUlong(bytes, start, length);
    38. //Console.WriteLine(ulong_number);
    39. return ulong_number;
    40. }
    41. private static ulong Example2(
    42. ReadOnlySpan<byte> bytes, int start, int length)
    43. {
    44. var ulong_number = ToUlongBytes(bytes, start, length);
    45. //Console.WriteLine(ulong_number);
    46. return ulong_number;
    47. }
    48. private static ulong ToUlong(
    49. ReadOnlySpan<byte> bits, int start, int length) =>
    50. length > 0 && length <= 64
    51. ? Convert.ToUInt64(ToBitsString(bits, start, length), 2)
    52. : 0;
    53. private static string ToBitsString(
    54. ReadOnlySpan<byte> bits, int start, int length)
    55. {
    56. var result = new StringBuilder();
    57. foreach (var bit in bits)
    58. result.Append(Convert.ToString(bit, 2).PadLeft(8, '0'));
    59. //Console.WriteLine(result.ToString());
    60. return result.ToString().Substring(start, length);
    61. }
    62. private static byte[] ToBytes(string bits) =>
    63. Enumerable.Range(0, bits.Length / 8).
    64. Select(x => Convert.ToByte(bits.Substring(x * 8, 8), 2)).ToArray();
    65. private static ulong ToUlongBytes(
    66. ReadOnlySpan<byte> bytes, int start, int length)
    67. {
    68. ulong result = 0;
    69. for (var i = 0; i < bytes.Length; i++)
    70. result |= Convert.ToUInt64(bytes[^(i + 1)]) << (i * 8);
    71. //pos von rechts gesehen
    72. var real_start = bytes.Length * 8 - start - length;
    73. result >>= real_start;
    74. result <<= 64 - length;
    75. result >>= 64 - length;
    76. return result;
    77. }
    78. private static byte[] RngBytes(int size)
    79. {
    80. var bytes = new byte[size];
    81. Random.Shared.NextBytes(bytes);
    82. return bytes;
    83. }
    84. }

    Vb.Net

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Imports System.Text
    4. Namespace ReadBitsFromMultiBytes
    5. Public Class Program
    6. Public Shared Sub Main()
    7. Test()
    8. Console.WriteLine()
    9. Console.WriteLine("FINISH")
    10. Console.WriteLine()
    11. Console.ReadLine()
    12. End Sub
    13. Public Shared Sub Test()
    14. For i = 0 To 10000 - 1
    15. Dim rand = Random.[Shared]
    16. Dim count = rand.[Next](2, 9)
    17. Dim bitlen = 8 * count
    18. Dim start = 0
    19. Dim length = Integer.MaxValue
    20. While start + length >= bitlen
    21. start = rand.[Next](bitlen \ 4, bitlen \ 2)
    22. length = rand.[Next](2, bitlen - start)
    23. End While
    24. Dim bytes = RngBytes(count)
    25. Dim ul1 = Example1(bytes, start, length)
    26. Dim ul2 = Example2(bytes, start, length)
    27. If ul1 <> ul2 Then Throw New Exception()
    28. Next
    29. End Sub
    30. Private Shared Function Example1(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
    31. Dim ulong_number = ToUlong(bytes, start, length)
    32. Return ulong_number
    33. End Function
    34. Private Shared Function Example2(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
    35. Dim ulong_number = ToUlongBytes(bytes, start, length)
    36. Return ulong_number
    37. End Function
    38. Private Shared Function ToUlong(bits As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
    39. Return If(length > 0 AndAlso length <= 64, Convert.ToUInt64(ToBitsString(bits, start, length), 2), 0UL)
    40. End Function
    41. Private Shared Function ToBitsString(bits As IEnumerable(Of Byte), start As Integer, length As Integer) As String
    42. Dim result = New StringBuilder()
    43. For Each bit In bits
    44. result.Append(Convert.ToString(bit, 2).PadLeft(8, "0"c))
    45. Next
    46. Return result.ToString().Substring(start, length)
    47. End Function
    48. Private Shared Function ToBytes(bits As String) As Byte()
    49. Return Enumerable.Range(0, bits.Length \ 8).[Select](Function(x) Convert.ToByte(bits.Substring(x * 8, 8), 2)).ToArray()
    50. End Function
    51. Private Shared Function ToUlongBytes(bytes As IEnumerable(Of Byte), start As Integer, length As Integer) As ULong
    52. Dim result = 0UL
    53. For i = 0 To bytes.Count - 1
    54. result = result Or Convert.ToUInt64(bytes(bytes.Count - i - 1)) << (i * 8)
    55. Next
    56. Dim real_start = bytes.Count * 8 - start - length
    57. result = result >> real_start
    58. result = result << (64 - length)
    59. result = result >> (64 - length)
    60. Return result
    61. End Function
    62. Private Shared Function RngBytes(size As Integer) As Byte()
    63. Dim bytes = New Byte(size - 1) {}
    64. Random.Shared.NextBytes(bytes)
    65. Return bytes
    66. End Function
    67. End Class
    68. End Namespace
    Dateien

    Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von „exc-jdbi“ ()

    Neu

    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.
    Zitat von mir 2023:
    Was interessiert mich Rechtschreibung? Der Compiler wird meckern wenn nötig :D

    Neu

    @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

    Neu

    Bartosz schrieb:

    Byte-Array nicht reversen


    Ja die gibt es.

    C#-Quellcode

    1. 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

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Neu

    @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".

    Zitat von mir 2023:
    Was interessiert mich Rechtschreibung? Der Compiler wird meckern wenn nötig :D

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „DTF“ ()

    Neu

    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

    1. ''' <summary>
    2. ''' <code>
    3. ''' 003 = 0000 0011
    4. ''' 148 = 1001 0100
    5. ''' Startposition (als Index) sei = 7 und bitCount sei = 6
    6. ''' 00000011 10010100
    7. ''' -------x xxxxx---
    8. ''' Ergibt (00)110010 = 50
    9. ''' </code>
    10. ''' </summary>
    11. ''' <param name="bytes"></param>
    12. ''' <param name="bitStartPositionAsIndex"></param>
    13. ''' <param name="bitCount"></param>
    14. ''' <returns></returns>
    15. Friend Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), bitStartPositionAsIndex As Integer, bitCount As Integer) As UInteger
    16. 'bytes = New Byte() {3, 148}
    17. 'bytes = New Byte() {5}
    18. 'bitCount = 3
    19. 'bitStartPositionAsIndex = 5
    20. If bitStartPositionAsIndex >= bytes.Length * 8 Then
    21. Throw New ArgumentException($"{NameOf(bitStartPositionAsIndex)} is too large ({bitStartPositionAsIndex}) for the byte array with a size of {bytes.Length}.")
    22. End If
    23. ' I want to use a loop to iterate backward from a specified start byte position to the end byte position,
    24. ' multiplying each byte by the corresponding power of 256.
    25. Dim big As UInt32 = 0UI
    26. Dim byteCount As Integer = CInt(Math.Ceiling(bitCount / 8.0))
    27. Dim byteStart As Integer = bitStartPositionAsIndex \ 8
    28. Dim cnt As Integer = 0
    29. Dim loopStart As Integer = Math.Min(byteCount + byteStart, bytes.Length - 1)
    30. For i As Integer = loopStart To byteStart Step -1
    31. big += bytes(i) * CUInt(Math.Pow(256, cnt))
    32. cnt += 1
    33. Next
    34. '----------------
    35. Dim mask As Integer = (1 << bitCount) - 1
    36. Dim toShift As Integer = ((bytes.Length * 8) - bitStartPositionAsIndex - bitCount)
    37. mask = mask << toShift
    38. Dim result As UInt32 = CUInt(big And mask)
    39. #If DEBUG Then
    40. Debug.WriteLine($"ExtractBitsAcrossBytesFromPositionRightAligned: {result >> toShift}")
    41. #End If
    42. Return result >> toShift
    43. End Function

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „Bartosz“ ()

    Neu

    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.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Bartosz“ ()

    Neu

    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.

    Neu

    @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

    1. ''' <summary>
    2. ''' <code>
    3. ''' Byte-Array {3, 148}
    4. ''' 003 = 0000 0011
    5. ''' 148 = 1001 0100
    6. ''' Startposition (als Index) sei = 7 und bitCount sei = 6
    7. ''' 00000011 10010100
    8. ''' -------x xxxxx---
    9. ''' Ergibt (00)110010 = 50
    10. ''' </code>
    11. ''' </summary>
    12. ''' <param name="bytes"></param>
    13. ''' <param name="bitStartPositionAsIndex"></param>
    14. ''' <param name="bitCount"></param>
    15. ''' <returns></returns>
    16. Private Shared Function ExtractBitsAcrossBytesFromPositionRightAligned(bytes As Byte(), bitStartPositionAsIndex As Integer, bitCount As Integer) As UInteger
    17. If bitStartPositionAsIndex >= bytes.Length * 8 Then
    18. Throw New ArgumentException($"{NameOf(bitStartPositionAsIndex)} is too large ({bitStartPositionAsIndex}) for the byte array with a size of {bytes.Length} bytes.")
    19. End If
    20. ' I want to use a loop to iterate backward from a specified start byte position to the end byte position,
    21. ' multiplying each byte by the corresponding power of 256.
    22. Dim big As UInt32 = 0UI
    23. Dim byteCount As Integer = CInt(Math.Ceiling(bitCount / 8.0))
    24. Dim byteStart As Integer = bitStartPositionAsIndex \ 8
    25. Dim cnt As Integer = 0
    26. Dim loopStart As Integer = Math.Min(byteCount + byteStart, bytes.Length - 1)
    27. For i As Integer = loopStart To byteStart Step -1
    28. big += bytes(i) * CUInt(Math.Pow(256, cnt))
    29. cnt += 1
    30. Next
    31. '----------------
    32. Dim mask As Integer = (1 << bitCount) - 1
    33. Dim toShift As Integer = ((bytes.Length * 8) - bitStartPositionAsIndex - bitCount)
    34. mask = mask << toShift
    35. Dim result As UInt32 = CUInt(big And mask)
    36. #If DEBUG Then
    37. Debug.WriteLine($"ExtractBitsAcrossBytesFromPositionRightAligned: {result >> toShift}")
    38. #End If
    39. Return result >> toShift
    40. End Function

    Neu

    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

    1. Public Function SubUInt(input As Byte(), start As Integer, length As Integer) As UInteger
    2. If length > 32 Then Throw New ArgumentException("length is too big. No more than 32 bits fit into UInt")
    3. Dim startIndex = start \ 8
    4. Dim remE As Integer
    5. Dim endIndex = Math.DivRem(start + length, 8, remE)
    6. Dim a = input.Skip(startIndex).Take(1 + endIndex - startIndex).Select(AddressOf Convert.ToUInt32).Aggregate(Function(x, y) x << 8 Or y)
    7. Return a >> (8 - remE) And ((CUInt(1) << length) - 1)
    8. End Function

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()