From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by mx.groups.io with SMTP id smtpd.web10.15689.1656530371400271688 for ; Wed, 29 Jun 2022 12:19:31 -0700 Authentication-Results: mx.groups.io; dkim=missing; spf=pass (domain: arm.com, ip: 217.140.110.172, mailfrom: pierre.gondois@arm.com) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 4D85B1480; Wed, 29 Jun 2022 12:19:31 -0700 (PDT) Received: from pierre123.home (unknown [172.31.20.19]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id C44F93F792; Wed, 29 Jun 2022 12:19:28 -0700 (PDT) From: "PierreGondois" To: devel@edk2.groups.io Cc: Sami Mujawar , Leif Lindholm , Ard Biesheuvel , Rebecca Cran , Michael D Kinney , Liming Gao , Jiewen Yao , Jian J Wang Subject: [PATCH RESEND v1 3/9] MdePkg/DrbgLib: Add BitStream implementation Date: Wed, 29 Jun 2022 21:18:40 +0200 Message-Id: <20220629191848.2619317-4-Pierre.Gondois@arm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220629191848.2619317-1-Pierre.Gondois@arm.com> References: <20220629191848.2619317-1-Pierre.Gondois@arm.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Pierre Gondois The Ctr Drbg does bitstream operations (additions, right/left shifting, ...). To have a clearer implementation of the NIST specifications, add a BitStream representation. Signed-off-by: Pierre Gondois Signed-off-by: Sami Mujawar --- MdePkg/Library/DrbgLib/BitStream.c | 1114 ++++++++++++++++++++++++++++ MdePkg/Library/DrbgLib/BitStream.h | 366 +++++++++ 2 files changed, 1480 insertions(+) create mode 100644 MdePkg/Library/DrbgLib/BitStream.c create mode 100644 MdePkg/Library/DrbgLib/BitStream.h diff --git a/MdePkg/Library/DrbgLib/BitStream.c b/MdePkg/Library/DrbgLib/= BitStream.c new file mode 100644 index 000000000000..1ae114fef803 --- /dev/null +++ b/MdePkg/Library/DrbgLib/BitStream.c @@ -0,0 +1,1114 @@ +/** @file + BitStream utility. + + Copyright (c) 2022, Arm Limited. All rights reserved.
+ SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#include +#include +#include +#include +#include + +#include "BitStream.h" + +/** Check whether a BitStream is NULL (null length). + + @param [in] Stream The BitStream. + + @retval TRUE if the BitStream is NULL (null length). + @retval FALSE otherwise. +**/ +BOOLEAN +EFIAPI +IsBitStreamEmpty ( + IN BIT_STREAM *Stream + ) +{ + return ((Stream =3D=3D NULL) || + (Stream->BitLen =3D=3D 0) || + (Stream->Data =3D=3D NULL)); +} + +/** Convert bits to bytes (rounds down). + + @param [in] Bits Bits. + + @return Bytes. +**/ +UINTN +EFIAPI +BitsToLowerBytes ( + IN UINTN Bits + ) +{ + return Bits >> 3; +} + +/** Convert bits to bytes (rounds up). + + @param [in] Bits Bits. + + @return Bytes. +**/ +UINTN +EFIAPI +BitsToUpperBytes ( + IN UINTN Bits + ) +{ + return ((Bits + 0x7) >> 3); +} + +/** Get the BitStream length (in bits). + + @param [in] Stream The BitStream. + + @return Length of the BitStream (in bits). +**/ +UINTN +EFIAPI +BitStreamBitLen ( + IN BIT_STREAM *Stream + ) +{ + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return 0; + } + + return Stream->BitLen; +} + +/** Get the BitStream length (in bytes). + + @param [in] Stream The BitStream. + + @return Length of the BitStream (in bytes). +**/ +UINTN +EFIAPI +BitStreamByteLen ( + IN BIT_STREAM *Stream + ) +{ + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return 0; + } + + return Stream->ByteLen; +} + +/** Get the BitStream data buffer. + + @param [in] Stream The BitStream. + + @return Data buffer of the BitStream (can be NULL). +**/ +UINT8 * +EFIAPI +BitStreamData ( + IN BIT_STREAM *Stream + ) +{ + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return 0; + } + + return Stream->Data; +} + +/** Clear the unsused bits of a Stream. + + For instance, if a stream is 5 bits long, then: + - bits[7:5] must be cleared. + - bits[4:0] must be preserved. + + @param [in, out] Stream The BitStream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +BitStreamClearUnusedBits ( + IN OUT BIT_STREAM *Stream + ) +{ + UINT8 UsedBits; + + if (IsBitStreamEmpty (Stream)) { + ASSERT (!IsBitStreamEmpty (Stream)); + return EFI_INVALID_PARAMETER; + } + + // Clear the unsused bits of the Stream. + // BitStream are big-endian, so MSByte is at index 0. + UsedBits =3D Stream->BitLen & 0x7; + if (UsedBits !=3D 0) { + Stream->Data[0] &=3D (0XFF >> (8 - UsedBits)); + } + + return EFI_SUCCESS; +} + +/** Allocate a buffer of BitLen (bits) for BitStream. + + @param [in] BitLen Length of the buffer to allocate (in bits). + @param [out] Stream The BitStream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +STATIC +EFI_STATUS +EFIAPI +BitStreamShallowAlloc ( + IN UINTN BitLen, + OUT BIT_STREAM *Stream + ) +{ + UINTN ByteLen; + + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + ZeroMem (Stream, sizeof (BIT_STREAM)); + + if (BitLen =3D=3D 0) { + return EFI_SUCCESS; + } + + ByteLen =3D BitsToUpperBytes (BitLen); + Stream->Data =3D (UINT8 *)AllocateZeroPool (ByteLen); + if (Stream->Data =3D=3D NULL) { + ASSERT (Stream->Data !=3D NULL); + return EFI_OUT_OF_RESOURCES; + } + + Stream->BitLen =3D BitLen; + Stream->ByteLen =3D ByteLen; + + return EFI_SUCCESS; +} + +/** Allocate a BitStream of BitLen (bits). + + @param [in] BitLen Length of the BitStream (in bits). + @param [out] Stream The BitStream to allocate. + Must be NULL initialized. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamAlloc ( + IN UINTN BitLen, + OUT BIT_STREAM **Stream + ) +{ + EFI_STATUS Status; + BIT_STREAM *LocStream; + + // Non NULL initialized pointers are considered invalid. + if ((Stream =3D=3D NULL) || + (*Stream !=3D NULL)) + { + ASSERT (Stream !=3D NULL); + ASSERT (*Stream =3D=3D NULL); + return EFI_INVALID_PARAMETER; + } + + LocStream =3D AllocateZeroPool (sizeof (BIT_STREAM)); + if (LocStream =3D=3D NULL) { + ASSERT (LocStream !=3D NULL); + return EFI_OUT_OF_RESOURCES; + } + + Status =3D BitStreamShallowAlloc (BitLen, LocStream); + if (EFI_ERROR (Status)) { + FreePool (LocStream); + ASSERT_EFI_ERROR (Status); + return Status; + } + + *Stream =3D LocStream; + + return EFI_SUCCESS; +} + +/** Free the buffer of the BitStream. + + This is a shallow free, so the BitStream structure itself if not freed= . + + @param [in, out] Stream BitStream to free the buffer of. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +BitStreamShallowFree ( + IN OUT BIT_STREAM *Stream + ) +{ + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + if (Stream->Data !=3D NULL) { + FreePool (Stream->Data); + } + + ZeroMem (Stream, sizeof (BIT_STREAM)); + + return EFI_SUCCESS; +} + +/** Free a BitStream. + + @param [in, out] Stream BitStream to free. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +BitStreamFree ( + IN OUT BIT_STREAM **Stream + ) +{ + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + BitStreamShallowFree (*Stream); + FreePool (*Stream); + *Stream =3D NULL; + + return EFI_SUCCESS; +} + +/** Initialize a BitStream with a buffer. + + The input Buffer is copied to a BitStream buffer. + + @param [in] Buffer Buffer to init the Data of the BitStream with. + The Buffer must be big-endian (MSByte at index= 0). + @param [in] BitLen Length of the Buffer (in bits). + @param [out] Stream BitStream to initialize. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamInit ( + IN CONST UINT8 *Buffer, + IN UINTN BitLen, + OUT BIT_STREAM **Stream + ) +{ + EFI_STATUS Status; + + // Non NULL initialized pointers are considered invalid. + if ((Stream =3D=3D NULL) || + (*Stream !=3D NULL) || + ((Buffer =3D=3D NULL) ^ (BitLen =3D=3D 0))) + { + ASSERT (Stream !=3D NULL); + ASSERT (*Stream =3D=3D NULL); + ASSERT (!((Buffer =3D=3D NULL) ^ (BitLen =3D=3D 0))); + return EFI_INVALID_PARAMETER; + } + + Status =3D BitStreamAlloc (BitLen, Stream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + + // BitStream are big-endian, i.e. MSByte is at index 0, + // so just copy the input Buffer. + CopyMem ((*Stream)->Data, Buffer, (*Stream)->ByteLen); + + return EFI_SUCCESS; +} + +/** Fill a Buffer with a Stream Data. + + The Buffer will be big-endian. + + @param [in] Stream Stream to take the Data from. + @param [out] Buffer Buffer where to write the Data. + Must be at least BitStreamByteLen (Stream) + bytes long. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +BitStreamToBuffer ( + IN BIT_STREAM *Stream, + OUT UINT8 *Buffer + ) +{ + if (IsBitStreamEmpty (Stream) || + (Buffer =3D=3D NULL)) + { + ASSERT (!IsBitStreamEmpty (Stream)); + ASSERT (Buffer !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + CopyMem (Buffer, Stream->Data, Stream->ByteLen); + + return EFI_SUCCESS; +} + +/** Shallow clone a BitStream. + + @param [out] StreamDest Shallow cloned BiStream. + @param [in] StreamSrc Source BitStream to shallow clone. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +BitStreamShallowClone ( + OUT BIT_STREAM *StreamDest, + IN BIT_STREAM *StreamSrc + ) +{ + if ((StreamDest =3D=3D NULL) || + (StreamSrc =3D=3D NULL)) + { + ASSERT (StreamDest !=3D NULL); + ASSERT (StreamSrc !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + CopyMem (StreamDest, StreamSrc, sizeof (BIT_STREAM)); + return EFI_SUCCESS; +} + +/** Clone a BitStream. + + @param [out] StreamDest Cloned BiStream. + @param [in] StreamSrc Source BitStream to clone. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamClone ( + OUT BIT_STREAM **StreamDest, + IN BIT_STREAM *StreamSrc + ) +{ + EFI_STATUS Status; + + if ((StreamDest =3D=3D NULL) || + (StreamSrc =3D=3D NULL)) + { + ASSERT (StreamDest !=3D NULL); + ASSERT (StreamSrc !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + Status =3D BitStreamInit (StreamSrc->Data, StreamSrc->BitLen, StreamDe= st); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + // Fall through. + } + + return Status; +} + +/** Replace an initialized BitStream with another. + + This function frees StreamRepl's Data if success. + + @param [in, out] StreamRepl Stream whose content is replaced. + @param [in] StreamData Stream containing the Data to use. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamReplace ( + IN OUT BIT_STREAM *StreamRepl, + IN BIT_STREAM *StreamData + ) +{ + EFI_STATUS Status; + + if ((StreamRepl =3D=3D NULL) || + (StreamData =3D=3D NULL)) + { + ASSERT (StreamRepl !=3D NULL); + ASSERT (StreamData !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + Status =3D BitStreamShallowFree (StreamRepl); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + + Status =3D BitStreamShallowClone (StreamRepl, StreamData); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + // StreamRepl's content was freed. Can't do much now. + // Fall through. + } + + return Status; +} + +/** Write a buffer to a BitStream. + + @param [in] Buffer Buffer to write to the BitStream. + Buffer is big-endian. + @param [in] StartBitIndex Bit index to start writing from. + @param [in] BitCount Count of bits to write. + @param [in, out] Stream BitStream to write to. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamWrite ( + IN UINT8 *Buffer, + IN UINTN StartBitIndex, + IN UINTN BitCount, + IN OUT BIT_STREAM *Stream + ) +{ + UINTN EndByteIndex; + UINTN EndBitIndex; + UINT8 StartBitRemainder; + UINT8 EndBitRemainder; + UINT8 *Data; + UINT8 ShiftR; + UINT8 ShiftL; + UINT8 BitMask; + UINTN ByteCount; + + if (((Buffer !=3D NULL) ^ (BitCount !=3D 0)) || + IsBitStreamEmpty (Stream) || + (StartBitIndex > (MAX_UINTN - BitCount)) || + ((StartBitIndex + BitCount) > Stream->BitLen)) + { + ASSERT (!((Buffer !=3D NULL) ^ (BitCount !=3D 0))); + ASSERT (!IsBitStreamEmpty (Stream)); + ASSERT (StartBitIndex <=3D (MAX_UINTN - BitCount)); + ASSERT ((StartBitIndex + BitCount) <=3D Stream->BitLen); + return EFI_INVALID_PARAMETER; + } + + ByteCount =3D BitsToUpperBytes (BitCount); + + if (BitCount =3D=3D 0) { + // Nothing to do. + return EFI_SUCCESS; + } + + EndByteIndex =3D Stream->ByteLen - 1 - + BitsToLowerBytes (StartBitIndex + BitCount - 1); + EndBitIndex =3D StartBitIndex + BitCount; + Data =3D &Stream->Data[EndByteIndex]; + + StartBitRemainder =3D StartBitIndex & 0x7; + EndBitRemainder =3D EndBitIndex & 0x7; + + ShiftL =3D StartBitRemainder; + ShiftR =3D 8 - ShiftL; + + // BitCount might not be a multiple of 8. These MsBits can also + // be spread on 2 bytes (in StreamIn). + if ((StartBitRemainder < EndBitRemainder) || (EndBitRemainder =3D=3D 0= )) { + BitMask =3D 0xFF << StartBitRemainder; + if (EndBitRemainder !=3D 0) { + BitMask ^=3D 0xFF << EndBitRemainder; + } + + *Data =3D (*Data & ~BitMask) | ((*Buffer++ << ShiftL) & BitMask); + + ByteCount--; + BitCount -=3D (BitCount & 0x7); + + if (StartBitRemainder =3D=3D 0) { + Data++; + } + } else if (StartBitRemainder > EndBitRemainder) { + BitMask =3D ~(0xFF << EndBitRemainder); + *Data =3D (*Data & ~BitMask) | ((*Buffer >> ShiftR) & BitMask); + Data++; + + BitMask =3D 0xFF << StartBitRemainder; + *Data =3D (*Data & ~BitMask) | ((*Buffer++ << ShiftL) & BitMask); + + ByteCount--; + BitCount -=3D (ShiftR + 8 - EndBitRemainder); + } + + // else (StartBitRemainder =3D=3D EndBitRemainder), nothing to do + + // From here, (BitCount % 8) =3D=3D 0 so we copy whole bytes from the = Buffer. + // It doesn't mean we are byte-aligned, so check if the alignment of + // StartBitIndex. + if (ShiftL =3D=3D 0) { + // StartBitIndex is byte aligned, + if (ByteCount) { + CopyMem (Data, Buffer, ByteCount); + } + } else { + // StartBitIndex is not byte aligned. + BitMask =3D 0xFF << (StartBitIndex & 0x7); + while (ByteCount--) { + *Data =3D (*Data & BitMask) | ((*Buffer >> ShiftR) & ~BitMask); + Data++; + *Data =3D (*Data & ~BitMask) | ((*Buffer++ << ShiftL) & BitMask); + } + } + + return EFI_SUCCESS; +} + +/** XoR two BitStreams. + + We must have len(StremA) =3D len(StreamB) + + @param [in] StreamA BitStream A. + @param [in] StreamB BitStream B. + @param [out] StreamOut Output BitStream. + Can be *StreamA or *StreamB to replace their + content with the new stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamXor ( + IN BIT_STREAM *StreamA, + IN BIT_STREAM *StreamB, + OUT BIT_STREAM **StreamOut + ) +{ + EFI_STATUS Status; + BIT_STREAM *LocStream; + UINTN ByteLen; + UINTN *DataLocN; + UINT8 *DataLoc8; + UINTN *DataAN; + UINT8 *DataA8; + UINTN *DataBN; + UINT8 *DataB8; + UINTN ByteLenN; + UINTN ByteLen8; + UINTN Offset; + + if ((StreamA =3D=3D NULL) || + (StreamB =3D=3D NULL) || + (StreamOut =3D=3D NULL) || + (StreamA->BitLen !=3D StreamB->BitLen)) + { + ASSERT (StreamA !=3D NULL); + ASSERT (StreamB !=3D NULL); + ASSERT (StreamOut !=3D NULL); + ASSERT (StreamA->BitLen =3D=3D StreamB->BitLen); + return EFI_INVALID_PARAMETER; + } + + if (StreamB->BitLen =3D=3D 0) { + // Nothing to do. + return EFI_SUCCESS; + } + + if (*StreamOut =3D=3D StreamA) { + LocStream =3D StreamA; + } else if (*StreamOut =3D=3D StreamB) { + LocStream =3D StreamB; + } else { + LocStream =3D NULL; + + Status =3D BitStreamAlloc (StreamA->BitLen, &LocStream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + } + + ByteLen =3D StreamA->ByteLen; + + DataLocN =3D (UINTN *)LocStream->Data; + DataAN =3D (UINTN *)StreamA->Data; + DataBN =3D (UINTN *)StreamB->Data; + // Speed up the process by taking chunks of UINTN instead of UINT8. + // ((sizeof (UINTN) >> 2) + 1) is 3 or 2 depending on the size of UINT= N. + ByteLenN =3D ByteLen >> (((sizeof (UINTN) >> 2) + 1)); + ByteLen8 =3D ByteLen & ((sizeof (UINTN) - 1)); + while (ByteLenN-- > 0) { + DataLocN[ByteLenN] =3D DataAN[ByteLenN] ^ DataBN[ByteLenN]; + } + + // XOR remaining UINT8 chunks. + if (ByteLen8 !=3D 0) { + Offset =3D ByteLen - ByteLen8; + DataLoc8 =3D (UINT8 *)DataLocN + Offset; + DataA8 =3D (UINT8 *)DataAN + Offset; + DataB8 =3D (UINT8 *)DataBN + Offset; + while (ByteLen8-- > 0) { + DataLoc8[ByteLen8] =3D DataA8[ByteLen8] ^ DataB8[ByteLen8]; + } + } + + *StreamOut =3D LocStream; + return EFI_SUCCESS; +} + +/** Concatenate two BitStreams. + + @param [in] StreamHigh BitStream containing the MSBytes. + @param [in] StreamLow BitStream containing the LSBytes. + @param [out] StreamOut Output BitStream. + Can be *StreamHigh or *StreamLow to replace t= heir + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamConcat ( + IN BIT_STREAM *StreamHigh, + IN BIT_STREAM *StreamLow, + OUT BIT_STREAM **StreamOut + ) +{ + EFI_STATUS Status; + BIT_STREAM LocStream; + UINTN TotalBitLen; + + if ((StreamHigh =3D=3D NULL) || + (StreamLow =3D=3D NULL) || + (StreamOut =3D=3D NULL)) + { + ASSERT (StreamHigh !=3D NULL); + ASSERT (StreamLow !=3D NULL); + ASSERT (StreamOut !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + TotalBitLen =3D StreamHigh->BitLen + StreamLow->BitLen; + + Status =3D BitStreamShallowAlloc (TotalBitLen, &LocStream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + + // Write StreamLow data. + Status =3D BitStreamWrite ( + StreamLow->Data, + 0, + StreamLow->BitLen, + &LocStream + ); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + + // Write StreamHigh data. + Status =3D BitStreamWrite ( + StreamHigh->Data, + StreamLow->BitLen, + StreamHigh->BitLen, + &LocStream + ); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + + if (*StreamOut =3D=3D StreamHigh) { + Status =3D BitStreamReplace (StreamHigh, &LocStream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + } else if (*StreamOut =3D=3D StreamLow) { + Status =3D BitStreamReplace (StreamLow, &LocStream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + } else { + Status =3D BitStreamClone (StreamOut, &LocStream); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + } + + return Status; + +ErrorHandler: + BitStreamShallowFree (&LocStream); + return Status; +} + +/** Select bits in a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] StartBitIndex Bit index to start the copy from. + @param [in] BitCount Count of bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream= . + Otherwise, it is initialized and contain= s the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamSelect ( + IN BIT_STREAM *StreamIn, + IN UINTN StartBitIndex, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ) +{ + EFI_STATUS Status; + BIT_STREAM StreamDest; + UINTN ByteCount; + UINTN EndByteIndex; + UINTN EndBitCountRemainder; + UINT8 *DataDest; + UINT8 *DataIn; + UINT8 ShiftR; + UINT8 ShiftL; + + if ((StreamIn =3D=3D NULL) || + (StartBitIndex > (MAX_UINTN - BitCount)) || + ((StartBitIndex + BitCount) > StreamIn->BitLen) || + (StreamOut =3D=3D NULL)) + { + ASSERT (StreamIn !=3D NULL); + ASSERT (StartBitIndex <=3D (MAX_UINTN - BitCount)); + ASSERT ((StartBitIndex + BitCount) <=3D StreamIn->BitLen); + ASSERT (StreamOut !=3D NULL); + return EFI_INVALID_PARAMETER; + } + + if (BitCount =3D=3D 0) { + if (*StreamOut =3D=3D StreamIn) { + Status =3D BitStreamShallowAlloc (0, &StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + + Status =3D BitStreamReplace (StreamIn, &StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + BitStreamShallowFree (&StreamDest); + // Fall through. + } + } else { + Status =3D BitStreamAlloc (0, StreamOut); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + // Fall through. + } + } + + return Status; + } + + ByteCount =3D BitsToUpperBytes (BitCount); + + // Alloc StreamDest. + Status =3D BitStreamShallowAlloc (BitCount, &StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + return Status; + } + + DataDest =3D StreamDest.Data; + + EndByteIndex =3D StreamIn->ByteLen - 1 - + BitsToLowerBytes (StartBitIndex + BitCount - 1); + DataIn =3D &StreamIn->Data[EndByteIndex]; + + ShiftR =3D StartBitIndex & 0x7; + if (ShiftR =3D=3D 0) { + // StartBitIndex is byte aligned. + CopyMem (DataDest, DataIn, ByteCount); + // Unused bits are cleared later. + } else { + // StartBitIndex is not byte aligned. + ShiftL =3D 8 - ShiftR; + + // BitCount might not be a multiple of 8. These MsBits can also + // be spread on 2 bytes (in StreamIn). + EndBitCountRemainder =3D BitCount & 0x7; + if ((ShiftR <=3D EndBitCountRemainder) || (EndBitCountRemainder =3D=3D= 0)) { + *DataDest |=3D (*DataIn++ << ShiftL); + } + + *DataDest++ |=3D (*DataIn >> ShiftR); + ByteCount -=3D 1; + + // Then copy 8 bits chunks. + while (ByteCount--) { + *DataDest |=3D (*DataIn++ << ShiftL); + *DataDest++ |=3D (*DataIn >> ShiftR); + } + } + + Status =3D BitStreamClearUnusedBits (&StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + + if (*StreamOut =3D=3D StreamIn) { + Status =3D BitStreamReplace (StreamIn, &StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + goto ErrorHandler; + } + } else { + Status =3D BitStreamClone (StreamOut, &StreamDest); + if (EFI_ERROR (Status)) { + ASSERT_EFI_ERROR (Status); + // Fall through. + } + } + + return Status; + +ErrorHandler: + BitStreamShallowFree (&StreamDest); + return Status; +} + +/** Get leftmost (i.e. MSBytes) BitLen bits of a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] BitCount Count of leftmost bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamLeftmost ( + IN BIT_STREAM *StreamIn, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ) +{ + if ((StreamIn =3D=3D NULL) || + (BitCount > StreamIn->BitLen)) + { + ASSERT (StreamIn !=3D NULL); + ASSERT (BitCount <=3D StreamIn->BitLen); + return EFI_INVALID_PARAMETER; + } + + return BitStreamSelect ( + StreamIn, + StreamIn->BitLen - BitCount, + BitCount, + StreamOut + ); +} + +/** Get rightmost (i.e. LSBytes) BitLen bits of a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] BitCount Count of righttmost bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamRightmost ( + IN BIT_STREAM *StreamIn, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ) +{ + return BitStreamSelect (StreamIn, 0, BitCount, StreamOut); +} + +/** Add a value modulo 2^n to a BitStream. + + @param [in] Val Value to add. + @param [in] Modulo Modulo of the addition (2^Modulo). + @param [in, out] Stream BitStream where the addition happens. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamAddModulo ( + IN UINTN Val, + IN UINTN Modulo, + IN OUT BIT_STREAM *Stream + ) +{ + UINTN Index; + UINTN ByteLen; + UINT8 Carry; + UINT8 Trunc8Val; + UINT8 *Data; + + if (IsBitStreamEmpty (Stream) || + (Stream->BitLen !=3D Modulo)) + { + // Additions with BitLen !=3D Modulo are not handled for now. + ASSERT (!IsBitStreamEmpty (Stream)); + ASSERT (Stream->BitLen =3D=3D Modulo); + return EFI_INVALID_PARAMETER; + } + + Index =3D 0; + ByteLen =3D Stream->ByteLen; + while ((Val !=3D 0) && (Index < ByteLen)) { + Data =3D &Stream->Data[ByteLen - Index - 1]; + + // Only check for 8-bits overflow. If we exit the loop with Carry =3D= =3D 1, + // then this was an actual addition modulo X. + // [1-7]-bits overflows are cleared with BitStreamClearUnusedBits(). + Trunc8Val =3D (UINT8)Val; + Carry =3D (*Data > MAX_UINT8 - Trunc8Val) ? 1 : 0; + *Data +=3D Trunc8Val; + + Val >>=3D 8; + Val +=3D Carry; + + Index++; + } + + return BitStreamClearUnusedBits (Stream); +} + +/** Print a BitStream. + + @param [in] Stream Stream to print. +**/ +VOID +EFIAPI +BitStreamPrint ( + IN BIT_STREAM *Stream + ) +{ + UINTN ByteLen; + UINTN Index; + UINT8 HeadBits; + UINT8 Data; + UINT8 Bit; + + if (Stream =3D=3D NULL) { + ASSERT (Stream !=3D NULL); + return; + } + + HeadBits =3D Stream->BitLen & 0x7; + ByteLen =3D Stream->ByteLen; + Print (L"BitStream(%lu): {\n", Stream->BitLen); + Print (L" [Index] < 7 6 5 4 3 2 1 0 >\n"); + + if (Stream->BitLen =3D=3D 0) { + return; + } + + // Print most significant byte. + Data =3D Stream->Data[0]; + + Print (L" [%02lu] (0x%02x) <", ByteLen - 1, Data); + for (Index =3D 7; Index >=3D 0; Index--) { + if ((Index >=3D HeadBits) && (HeadBits !=3D 0)) { + Bit =3D 'x'; + } else { + Bit =3D '0' + ((Data & (1 << Index)) >> Index); + } + + Print (L" %c", Bit); + } + + Print (L" >\n"); + + // Print other bytes. + for (Index =3D 1; Index < ByteLen; Index++) { + Data =3D Stream->Data[Index]; + Print ( + L" [%02ld] (0x%02x) < %d %d %d %d %d %d %d %d >\n", + ByteLen - Index - 1, + Data, + Data >> 7, + (Data & 0x40) >> 6, + (Data & 0x20) >> 5, + (Data & 0x10) >> 4, + (Data & 0x8) >> 3, + (Data & 0x4) >> 2, + (Data & 0x2) >> 1, + (Data & 0x1) + ); + } + + Print (L"}\n"); +} diff --git a/MdePkg/Library/DrbgLib/BitStream.h b/MdePkg/Library/DrbgLib/= BitStream.h new file mode 100644 index 000000000000..6f0c7732b2a5 --- /dev/null +++ b/MdePkg/Library/DrbgLib/BitStream.h @@ -0,0 +1,366 @@ +/** @file + BitStream utility. + + Copyright (c) 2022, Arm Limited. All rights reserved.
+ SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#ifndef BIT_STREAM_H_ +#define BIT_STREAM_H_ + +/** BitStream. + + Struct holding a buffer of data and allowing to do operations + on them (concatenation, selecting rightmost bits, addition, ...). + BitStream are big-endian (MSByte at index 0). +*/ +typedef struct BitStream { + /// Length of BitStream in bits. + UINTN BitLen; + /// Length of BitStream in bytes. + UINTN ByteLen; + /// Buffer holding the data. + UINT8 *Data; +} BIT_STREAM; + +/** Check whether a BitStream is NULL (null length). + + @param [in] Stream The BitStream. + + @retval TRUE if the BitStream is NULL (null length). + @retval FALSE otherwise. +**/ +BOOLEAN +EFIAPI +IsBitStreamEmpty ( + IN BIT_STREAM *Stream + ); + +/** Convert bits to bytes (rounds down). + + @param [in] Bits Bits. + + @return Bytes. +**/ +UINTN +EFIAPI +BitsToLowerBytes ( + IN UINTN Bits + ); + +/** Convert bits to bytes (rounds up). + + @param [in] Bits Bits. + + @return Bytes. +**/ +UINTN +EFIAPI +BitsToUpperBytes ( + IN UINTN Bits + ); + +/** Get the BitStream length (in bits). + + @param [in] Stream The BitStream. + + @return Length of the BitStream (in bits). +**/ +UINTN +EFIAPI +BitStreamBitLen ( + IN BIT_STREAM *Stream + ); + +/** Get the BitStream length (in bytes). + + @param [in] Stream The BitStream. + + @return Length of the BitStream (in bytes). +**/ +UINTN +EFIAPI +BitStreamByteLen ( + IN BIT_STREAM *Stream + ); + +/** Get the BitStream data buffer. + + @param [in] Stream The BitStream. + + @return Data buffer of the BitStream (can be NULL). +**/ +UINT8 * +EFIAPI +BitStreamData ( + IN BIT_STREAM *Stream + ); + +/** Allocate a BitStream of BitLen (bits). + + @param [in] BitLen Length of the BitStream (in bits). + @param [out] Stream The BitStream to allocate. + Must be NULL initialized. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamAlloc ( + IN UINTN BitLen, + OUT BIT_STREAM **Stream + ); + +/** Free a BitStream. + + @param [in, out] Stream BitStream to free. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +BitStreamFree ( + IN OUT BIT_STREAM **Stream + ); + +/** Initialize a BitStream with a buffer. + + The input Buffer is copied to a BitStream buffer. + + @param [in] Buffer Buffer to init the Data of the BitStream with. + The Buffer must be big-endian (MSByte at index= 0). + @param [in] BitLen Length of the Buffer (in bits). + @param [out] Stream BitStream to initialize. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamInit ( + IN CONST UINT8 *Buffer, + IN UINTN BitLen, + OUT BIT_STREAM **Stream + ); + +/** Fill a Buffer with a Stream Data. + + The Buffer will be big-endian. + + @param [in] Stream Stream to take the Data from. + @param [out] Buffer Buffer where to write the Data. + Must be at least BitStreamByteLen (Stream) + bytes long. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +BitStreamToBuffer ( + IN BIT_STREAM *Stream, + OUT UINT8 *Buffer + ); + +/** Clone a BitStream. + + @param [out] StreamDest Cloned BiStream. + @param [in] StreamSrc Source BitStream to clone. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamClone ( + OUT BIT_STREAM **StreamDest, + IN BIT_STREAM *StreamSrc + ); + +/** Replace an initialized BitStream with another. + + This function frees StreamRepl's Data if success. + + @param [out] StreamRepl Stream whose content is replaced. + @param [in] StreamData Stream containing the Data to use. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamReplace ( + IN OUT BIT_STREAM *StreamRepl, + IN BIT_STREAM *StreamData + ); + +/** Write a buffer to a BitStream. + + @param [in] Buffer Buffer to write to the BitStream. + Buffer is big-endian. + @param [in] StartBitIndex Bit index to start writing from. + @param [in] BitCount Count of bits to write. + @param [in, out] Stream BitStream to write to. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamWrite ( + IN UINT8 *Buffer, + IN UINTN StartBitIndex, + IN UINTN BitCount, + IN OUT BIT_STREAM *Stream + ); + +/** XoR two BitStreams. + + We must have len(StremA) =3D len(StreamB) + + @param [in] StreamA BitStream A. + @param [in] StreamB BitStream B. + @param [out] StreamOut Output BitStream. + Can be *StreamA or *StreamB to replace their + content with the new stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamXor ( + IN BIT_STREAM *StreamA, + IN BIT_STREAM *StreamB, + OUT BIT_STREAM **StreamOut + ); + +/** Concatenate two BitStreams. + + @param [in] StreamHigh BitStream containing the MSBytes. + @param [in] StreamLow BitStream containing the LSBytes. + @param [out] StreamOut Output BitStream. + Can be *StreamHigh or *StreamLow to replace t= heir + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamConcat ( + IN BIT_STREAM *StreamHigh, + IN BIT_STREAM *StreamLow, + OUT BIT_STREAM **StreamOut + ); + +/** Select bits in a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] StartBitIndex Bit index to start the copy from. + @param [in] BitCount Count of bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream= . + Otherwise, it is initialized and contain= s the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamSelect ( + IN BIT_STREAM *StreamIn, + IN UINTN StartBitIndex, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ); + +/** Get leftmost (i.e. MSBytes) BitLen bits of a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] BitCount Count of leftmost bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamLeftmost ( + IN BIT_STREAM *StreamIn, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ); + +/** Get rightmost (i.e. LSBytes) BitLen bits of a BitStream. + + @param [in] StreamIn Input BitStream. + @param [in] BitCount Count of righttmost bits to copy. + @param [out] StreamOut Output BitStream. + Can be *StreamIn to replace its + content with the new concatenated stream. + Otherwise, it is initialized and contains the + resulting stream. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamRightmost ( + IN BIT_STREAM *StreamIn, + IN UINTN BitCount, + OUT BIT_STREAM **StreamOut + ); + +/** Add a value modulo 2^n to a BitStream. + + @param [in] Val Value to add. + @param [in] Modulo Modulo of the addition (2^Modulo). + @param [in, out] Stream BitStream where the addition happens. + + @retval EFI_SUCCESS Success. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Out of resources. +**/ +EFI_STATUS +EFIAPI +BitStreamAddModulo ( + IN UINTN Val, + IN UINTN Modulo, + IN OUT BIT_STREAM *Stream + ); + +/** Print a BitStream. + + @param [in] Stream Stream to print. +**/ +VOID +EFIAPI +BitStreamPrint ( + IN BIT_STREAM *Stream + ); + +#endif // BIT_STREAM_H_ --=20 2.25.1