From 6c6c850ad62d6fdc73828057339be1dc7df37c8e Mon Sep 17 00:00:00 2001 From: darylm503 Date: Tue, 11 Dec 2012 21:19:14 +0000 Subject: StdLib: Add terminal type line editing (Interactive IO) for console devices. Adds a subset of the terminal I/O capabilities described in the Single Unix Specification, V4. Supports: Erase previous character. Default is Backspace or ^H Erase line. Default is ^U TAB characters are supported and, by default, are rendered as 8 spaces. They will still be read as a single TAB character. Both Canonical and Non-Canonical modes are supported. If a terminal device is opened with O_TTY_INIT in the mode, the device will be initialized to "sane" values for interactive use. It will be in Canonical mode, Enter will be translated to NewLine and on output, a NewLine is translated to CRLF. Echoing will be on, control characters are output as ^X, and TABs are expanded. See the new file for more information. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: daryl.mcdaniel@intel.com Reviewed-by: erik.c.bjorge@intel.com Reviewed-by: leroy.p.leahy@intel.com Reviewed-by: lee.g.rosenbaum@intel.com Reviewed-by: jaben.carsey@intel.com git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@13989 6f19259b-4bc3-4df7-8a09-765794883524 --- StdLib/LibC/Containers/Common/ModuloUtil.c | 149 ++++++++ StdLib/LibC/Containers/ContainerLib.inf | 46 +++ StdLib/LibC/Containers/Queues/Fifo.c | 526 +++++++++++++++++++++++++++++ 3 files changed, 721 insertions(+) create mode 100644 StdLib/LibC/Containers/Common/ModuloUtil.c create mode 100644 StdLib/LibC/Containers/ContainerLib.inf create mode 100644 StdLib/LibC/Containers/Queues/Fifo.c (limited to 'StdLib/LibC/Containers') diff --git a/StdLib/LibC/Containers/Common/ModuloUtil.c b/StdLib/LibC/Containers/Common/ModuloUtil.c new file mode 100644 index 0000000000..5f75698bd6 --- /dev/null +++ b/StdLib/LibC/Containers/Common/ModuloUtil.c @@ -0,0 +1,149 @@ +/** @file + Utility functions for performing basic math operations constrained within a + modulus. + + These functions are intended to simplify small changes to a value which much + remain within a specified modulus. + + NOTE: Changes must be less than or equal to the modulus specified by MaxVal. + + Copyright (c) 2012, Intel Corporation. All rights reserved.
+ This program and the accompanying materials are licensed and made available + under the terms and conditions of the BSD License which accompanies this + distribution. The full text of the license may be found at + http://opensource.org/licenses/bsd-license.php. + + THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, + WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. +**/ +#include +#include +#include + +/** Counter = (Counter + 1) % MaxVal; + + Counter is always expected to be LESS THAN MaxVal. + 0 <= Counter < MaxVal + + @param[in] Counter The value to be incremented. + @param[in] MaxVal Modulus of the operation. + + @return Returns the result of incrementing Counter, modulus MaxVal. + If Counter >= MaxVal, returns -1. +**/ +INT32 +EFIAPI +ModuloIncrement( + UINT32 Counter, + UINT32 MaxVal + ) +{ + INT32 Temp; + + if(Counter < MaxVal) { + Temp = (INT32)(Counter + 1); + if(Temp >= (INT32)MaxVal) { + Temp = 0; + } + } + else { + Temp = -1; + } + return Temp; +} + +/** Counter = (Counter - 1) % MaxVal; + + Counter is always expected to be LESS THAN MaxVal. + 0 <= Counter < MaxVal + + @param[in] Counter The value to be decremented. + @param[in] MaxVal Modulus of the operation. + + @return Returns the result of decrementing Counter, modulus MaxVal. + If Counter >= MaxVal, returns -1. +**/ +INT32 +EFIAPI +ModuloDecrement( + UINT32 Counter, + UINT32 MaxVal + ) +{ + INT32 Temp; + + if(Counter < MaxVal) { + Temp = (INT32)Counter - 1; + // If Counter is zero, Temp will become -1. + if(Temp < 0) { + Temp = (INT32)MaxVal - 1; + } + } + else { + Temp = -1; + } + + return Temp; +} + +/** Decrement Counter but don't decrement past zero. + + @param[in] Counter The value to be decremented. + + @return Returns the result of decrementing Counter. +**/ +UINT32 +EFIAPI +BoundDecrement( + UINT32 Counter + ) +{ + return ((Counter > 0) ? (Counter - 1) : 0); +} + +/** Increment Counter but don't increment past MaxVal. + Counter should be maintained in the range (0 <= Counter < MaxVal). + + @param[in] Counter The value to be decremented. + @param[in] MaxVal The upper bound for Counter. + + @return Returns the result of incrementing Counter. +**/ +UINT32 +EFIAPI +BoundIncrement( + UINT32 Counter, + UINT32 MaxVal + ) +{ + return ((Counter < (MaxVal - 1)) ? (Counter + 1) : (MaxVal - 1)); +} + +/** Counter = (Counter + Increment) % MaxVal; + + @param[in] Counter The value to be incremented. + @param[in] Increment The value to add to Counter. + @param[in] MaxVal Modulus of the operation. + + @return Returns the result of adding Increment to Counter, modulus MaxVal, + or -1 if Increment is larger than MaxVal. +**/ +INT32 +EFIAPI +ModuloAdd ( + UINT32 Counter, + UINT32 Increment, + UINT32 MaxVal + ) +{ + UINT32 Temp; + + if(Increment > MaxVal) { + return -1; + } + Temp = (Counter + Increment); + while(Temp >= MaxVal) { + Temp -= MaxVal; + } + return Temp; +} diff --git a/StdLib/LibC/Containers/ContainerLib.inf b/StdLib/LibC/Containers/ContainerLib.inf new file mode 100644 index 0000000000..4ca6690c4d --- /dev/null +++ b/StdLib/LibC/Containers/ContainerLib.inf @@ -0,0 +1,46 @@ +## @file +# INF file for building the Container library. +# +# Various types of containers are implemented within this library. +# Types of containers may be Queues (FIFO, LIFO, etc.), hash tables, etc. +# +# Copyright (c) 2012, Intel Corporation. All rights reserved.
+# This program and the accompanying materials are licensed and made available +# under the terms and conditions of the BSD License which accompanies this +# distribution. The full text of the license may be found at +# http://opensource.org/licenses/bsd-license.php +# +# THIS PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, +# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. +# +## + +[Defines] + INF_VERSION = 0x00010005 + BASE_NAME = LibContainer + FILE_GUID = 92f7436e-7395-4da1-a7be-f352f0bcd79c + MODULE_TYPE = UEFI_APPLICATION + VERSION_STRING = 1.0 + LIBRARY_CLASS = LibContainer + +# +# The following information is for reference only and not required by the build tools. +# +# VALID_ARCHITECTURES = IA32 X64 +# + +[Sources] + Queues/Fifo.c + Common/ModuloUtil.c + +[LibraryClasses] + BaseLib + BaseMemoryLib + MemoryAllocationLib + LibC + LibWchar + +[Packages] + MdePkg/MdePkg.dec + StdLib/StdLib.dec + StdLibPrivateInternalFiles/DoNotUse.dec diff --git a/StdLib/LibC/Containers/Queues/Fifo.c b/StdLib/LibC/Containers/Queues/Fifo.c new file mode 100644 index 0000000000..347ac02fd2 --- /dev/null +++ b/StdLib/LibC/Containers/Queues/Fifo.c @@ -0,0 +1,526 @@ +/** @file + Class for arbitrary sized FIFO queues. + + The FIFO is empty if both the Read and Write indexes are equal. + The FIFO is full if the next write would make the Read and Write indexes equal. + + Member variable NumElements is the maximum number of elements that can be + contained in the FIFO. + If NumElements is ZERO, there is an error. + NumElements should be in the range 1:N. + + Members WriteIndex and ReadIndex are indexes into the array implementing the + FIFO. They should be in the range 0:(NumElements - 1). + + One element of the FIFO is always reserved as the "terminator" element. Thus, + the capacity of a FIFO is actually NumElements-1. + + Copyright (c) 2012, Intel Corporation. All rights reserved.
+ This program and the accompanying materials are licensed and made available + under the terms and conditions of the BSD License which accompanies this + distribution. The full text of the license may be found at + http://opensource.org/licenses/bsd-license.php. + + THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, + WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. +**/ +#include +#include +#include +#include + +#include + +#include +#include +#include +#include +#include +#include + +/** Determine number of items available to read from the FIFO. + + The number of items are either the number of bytes, or the number of elements + depending upon the value of the As enumerator. + + @param[in] Self Pointer to the FIFO instance. + @param[in] As An enumeration variable whose value determines whether the + returned value is the number of bytes or the number of elements + currently contained by the FIFO. + + @retval 0 The FIFO is empty. + @retval >=0 The number of items contained by the FIFO. +**/ +static +size_t +EFIAPI +FIFO_NumInQueue ( + cFIFO *Self, + FIFO_ElemBytes As +) +{ + size_t Count; + + if(Self->ReadIndex <= Self->WriteIndex) { + Count = Self->WriteIndex - Self->ReadIndex; + } + else { + Count = Self->NumElements - (Self->ReadIndex - Self->WriteIndex); + } + if(As == AsBytes) { + Count *= Self->ElementSize; + } + return Count; +} + +/** Determine amount of free space in the FIFO that can be written into. + + The number of items are either the number of bytes, or the number of elements + depending upon the value of the As enumerator. + + @param[in] Self Pointer to the FIFO instance. + @param[in] As An enumeration variable whose value determines whether the + returned value is the number of bytes or the number of elements + currently available in the FIFO. + + @retval 0 The FIFO is full. + @retval >=0 The number of items which can be accepted by the FIFO. +**/ +static +size_t +EFIAPI +FIFO_FreeSpace ( + cFIFO *Self, + FIFO_ElemBytes As +) +{ + size_t Count; + UINT32 RDex; + UINT32 WDex; + + RDex = Self->ReadIndex; + WDex = Self->WriteIndex; + + if(RDex <= WDex) { + Count = Self->NumElements - ((WDex - RDex) - 1); + } + else { + Count = (RDex - WDex); + } + if(As == AsBytes) { + Count *= Self->ElementSize; + } + return Count; +} + +/** Reduce the FIFO contents by NumElem elements. + + @param[in] Self Pointer to the FIFO instance. + @param[in] NumElem Number of elements to delete from the FIFO. + + @retval 0 FIFO is now empty. + @retval N>0 There are still N elements in the FIFO. + @retval -1 There are fewer than NumElem elements in the FIFO. +**/ +static +ssize_t +FIFO_Reduce ( + cFIFO *Self, + size_t NumElem + ) +{ + size_t QCount; + ssize_t RetVal; + + assert(Self != NULL); + + QCount = FIFO_NumInQueue(Self, AsElements); + if(NumElem > QCount) { + RetVal = -1; + errno = EINVAL; + } + else { + RetVal = (ssize_t)ModuloAdd(Self->ReadIndex, (UINT32)NumElem, Self->NumElements); + Self->ReadIndex = (UINT32)RetVal; + + RetVal = (ssize_t)(QCount - NumElem); + } + return RetVal; +} + +/** Test whether the FIFO is empty. + + @param[in] Self Pointer to the FIFO instance. + + @retval TRUE The FIFO is empty. + @retval FALSE There is data in the FIFO. +**/ +static +BOOLEAN +EFIAPI +FIFO_IsEmpty ( + cFIFO *Self + ) +{ + assert(Self != NULL); + + return (BOOLEAN)(Self->WriteIndex == Self->ReadIndex); +} + +/** Test whether the FIFO is full. + + @param[in] Self Pointer to the FIFO instance. + + @retval TRUE The FIFO is full. + @retval FALSE There is free space in the FIFO. +**/ +static +BOOLEAN +EFIAPI +FIFO_IsFull ( + cFIFO *Self + ) +{ + assert(Self != NULL); + + return (BOOLEAN)(ModuloIncrement(Self->WriteIndex, Self->NumElements) == (INT32)Self->ReadIndex); +} + +/** Add one or more elements to the FIFO. + + This function allows one to add one or more elements, as specified by Count, + to the FIFO. Each element is of the size specified when the FIFO object + was instantiated (FIFO.ElementSize). + + pElement points to the first byte of the first element to be added. + If multiple elements are to be added, the elements are expected to be + organized as a packed array. + + @param[in] Self Pointer to the FIFO instance. + @param[in] pElement Pointer to the element(s) to enqueue (add). + @param[in] Count Number of elements to add. + + @retval 0 The FIFO is full. + @retval >=0 The number of elements added to the FIFO. +**/ +static +size_t +EFIAPI +FIFO_Enqueue ( + cFIFO *Self, + const void *pElement, + size_t Count + ) +{ + uintptr_t ElemPtr; + uintptr_t QPtr; + size_t i; + UINT32 SizeOfElement; + UINT32 Windex; + + assert(Self != NULL); + assert(pElement != NULL); + assert(Count >= 0); + + if(FIFO_IsFull(Self)) { + Count = 0; + } + else { + Count = MIN(Count, Self->FreeSpace(Self, AsElements)); + SizeOfElement = Self->ElementSize; + Windex = Self->WriteIndex; + + ElemPtr = (uintptr_t)pElement; + + QPtr = (uintptr_t)Self->Queue + (SizeOfElement * Windex); + for(i = 0; i < Count; ++i) { + (void)CopyMem((void *)QPtr, (const void *)ElemPtr, SizeOfElement); + Windex = (UINT32)ModuloIncrement(Windex, Self->NumElements); + if(Windex == 0) { // If the index wrapped + QPtr = (uintptr_t)Self->Queue; + } + else { + QPtr += SizeOfElement; + } + ElemPtr += SizeOfElement; + } + (void)ZeroMem((void*)QPtr, SizeOfElement); + Self->WriteIndex = Windex; + } + return Count; +} + +/** Read or copy elements from the FIFO. + + This function allows one to read one or more elements, as specified by Count, + from the FIFO. Each element is of the size specified when the FIFO object + was instantiated (FIFO.ElementSize). + + pElement points to the destination of the first byte of the first element + to be read. If multiple elements are to be read, the elements are expected + to be organized as a packed array. + + @param[in] Self Pointer to the FIFO instance. + @param[out] pElement Pointer to where to store the element(s) read from the FIFO. + @param[in] Count Number of elements to dequeue. + @param[in] Consume If TRUE, consume read elements. Otherwise, preserve. + + @retval 0 The FIFO is empty. + @retval >=0 The number of elements read from the FIFO. +**/ +static +size_t +EFIAPI +FIFO_Dequeue ( + cFIFO *Self, + void *pElement, + size_t Count, + BOOLEAN Consume + ) +{ + UINTN ElemPtr; + UINTN QPtr; + UINT32 RDex; + UINT32 SizeOfElement; + UINT32 i; + + assert(Self != NULL); + assert(pElement != NULL); + assert(Count != 0); + + if(FIFO_IsEmpty(Self)) { + Count = 0; + } + else { + RDex = Self->ReadIndex; + SizeOfElement = Self->ElementSize; + ElemPtr = (UINTN)pElement; + Count = MIN(Count, Self->Count(Self, AsElements)); + + QPtr = (UINTN)Self->Queue + (RDex * Self->ElementSize); + for(i = 0; i < Count; ++i) { + (void)CopyMem((void *)ElemPtr, (const void *)QPtr, Self->ElementSize); + RDex = (UINT32)ModuloIncrement(RDex, Self->NumElements); + if(RDex == 0) { // If the index wrapped + QPtr = (UINTN)Self->Queue; + } + else { + QPtr += Self->ElementSize; + } + ElemPtr += Self->ElementSize; + } + if(Consume) { + Self->ReadIndex = RDex; + } + } + return Count; +} + +/** Read elements from the FIFO. + + @param[in] Self Pointer to the FIFO instance. + @param[out] pElement Pointer to where to store the element read from the FIFO. + @param[in] Count Number of elements to dequeue. + + @retval 0 The FIFO is empty. + @retval >=0 The number of elements read from the FIFO. +**/ +static +size_t +EFIAPI +FIFO_Read ( + cFIFO *Self, + void *pElement, + size_t Count + ) +{ + return FIFO_Dequeue(Self, pElement, Count, TRUE); +} + +/** Make a copy of the FIFO's data. + The contents of the FIFO is copied out and linearized without affecting the + FIFO contents. + + @param[in] Self Pointer to the FIFO instance. + @param[out] pElement Pointer to where to store the elements copied from the FIFO. + @param[in] Count Number of elements to copy. + + @retval 0 The FIFO is empty. + @retval >=0 The number of elements copied from the FIFO. +**/ +static +size_t +EFIAPI +FIFO_Copy ( + cFIFO *Self, + void *pElement, + size_t Count + ) +{ + return FIFO_Dequeue(Self, pElement, Count, FALSE); +} + +/** Get the FIFO's current Read Index. + + @param[in] Self Pointer to the FIFO instance. +**/ +static +UINT32 +EFIAPI +FIFO_GetRDex ( + cFIFO *Self +) +{ + assert(Self != NULL); + + return Self->ReadIndex; +} + +/** Get the FIFO's current Write Index. + + @param[in] Self Pointer to the FIFO instance. + + @return The current value of the FIFO's WriteIndex member is returned. +**/ +static +UINT32 +EFIAPI +FIFO_GetWDex ( + cFIFO *Self +) +{ + assert(Self != NULL); + + return Self->WriteIndex; +} + +/** Cleanly delete a FIFO instance. + + @param[in] Self Pointer to the FIFO instance. +**/ +static +void +EFIAPI +FIFO_Delete ( + cFIFO *Self + ) +{ + assert(Self != NULL); + + if(Self->Queue != NULL) { + FreePool(Self->Queue); + Self->Queue = NULL; // Zombie catcher + } + FreePool(Self); +} + +/** Empty the FIFO, discarding up to NumToFlush elements. + + @param[in] Self Pointer to the FIFO instance. + @param[in] NumToFlush Number of elements to flush from the FIFO. + If larger than the number of elements in the + FIFO, the FIFO is emptied. + + @return Returns the number of elements remaining in the FIFO after the flush. +**/ +static +size_t +EFIAPI +FIFO_Flush ( + cFIFO *Self, + size_t NumToFlush + ) +{ + size_t NumInQ; + size_t Remainder; + + assert(Self != NULL); + + NumInQ = FIFO_FreeSpace(Self, AsElements); + if(NumToFlush >= NumInQ) { + Self->ReadIndex = 0; + Self->WriteIndex = 0; + Remainder = 0; + } + else { + Remainder = FIFO_Reduce(Self, NumToFlush); + } + return Remainder; +} + +/** Remove the most recently added element from the FIFO. + + @param[in] Self Pointer to the FIFO instance. + + @return Returns the number of elements remaining in the FIFO. +**/ +static +size_t +EFIAPI +FIFO_Truncate ( + cFIFO *Self + ) +{ + size_t Remainder; + + assert(Self != NULL); + + Remainder = Self->Count(Self, AsElements); + if(Remainder > 0) { + Self->WriteIndex = (UINT32)ModuloDecrement(Self->WriteIndex, Self->NumElements); + --Remainder; + } + return Remainder; +} + +/** Construct a new instance of a FIFO Queue. + + @param[in] NumElements Number of elements to be contained in the new FIFO. + @param[in] ElementSize Size, in bytes, of an element. + + @retval NULL Unable to create the instance. + @retval NonNULL Pointer to the new FIFO instance. +**/ +cFIFO * +EFIAPI +New_cFIFO( + UINT32 NumElements, + size_t ElementSize + ) +{ + cFIFO *FIFO; + UINT8 *Queue; + + FIFO = NULL; + if((NumElements > 2) && (ElementSize > 0)) { + FIFO = (cFIFO *)AllocatePool(sizeof(cFIFO)); + if(FIFO != NULL) { + Queue = (UINT8 *)AllocateZeroPool(NumElements * ElementSize); + if(Queue != NULL) { + FIFO->Write = FIFO_Enqueue; + FIFO->Read = FIFO_Read; + FIFO->Copy = FIFO_Copy; + FIFO->IsEmpty = FIFO_IsEmpty; + FIFO->IsFull = FIFO_IsFull; + FIFO->Count = FIFO_NumInQueue; + FIFO->FreeSpace = FIFO_FreeSpace; + FIFO->Flush = FIFO_Flush; + FIFO->Truncate = FIFO_Truncate; + FIFO->Delete = FIFO_Delete; + FIFO->GetRDex = FIFO_GetRDex; + FIFO->GetWDex = FIFO_GetWDex; + + FIFO->Queue = Queue; + FIFO->ElementSize = (UINT32)ElementSize; + FIFO->NumElements = (UINT32)NumElements; + FIFO->ReadIndex = 0; + FIFO->WriteIndex = 0; + } + else { + FreePool(FIFO); + FIFO = NULL; + } + } + } + return FIFO; +} -- cgit v1.2.3