+ UINT64 SubLength;\r
+ UINT32 MtrrNumber;\r
+ BOOLEAN UseLeastAlignment;\r
+\r
+ UseLeastAlignment = TRUE;\r
+ SubLength = 0;\r
+\r
+ //\r
+ // Calculate the alignment of the base address.\r
+ //\r
+ for (MtrrNumber = 0; Length != 0; MtrrNumber++) {\r
+ if (UseLeastAlignment) {\r
+ SubLength = MtrrLibLeastAlignment (BaseAddress, Alignment0);\r
+\r
+ if (SubLength > Length) {\r
+ //\r
+ // Set a flag when remaining length is too small\r
+ // so that MtrrLibLeastAlignment() is not called in following loops.\r
+ //\r
+ UseLeastAlignment = FALSE;\r
+ }\r
+ }\r
+\r
+ if (!UseLeastAlignment) {\r
+ SubLength = GetPowerOfTwo64 (Length);\r
+ }\r
+\r
+ BaseAddress += SubLength;\r
+ Length -= SubLength;\r
+ }\r
+\r
+ return MtrrNumber;\r
+}\r
+\r
+/**\r
+ Return whether the left MTRR type precedes the right MTRR type.\r
+\r
+ The MTRR type precedence rules are:\r
+ 1. UC precedes any other type\r
+ 2. WT precedes WB\r
+ For further details, please refer the IA32 Software Developer's Manual,\r
+ Volume 3, Section "MTRR Precedences".\r
+\r
+ @param Left The left MTRR type.\r
+ @param Right The right MTRR type.\r
+\r
+ @retval TRUE Left precedes Right.\r
+ @retval FALSE Left doesn't precede Right.\r
+**/\r
+BOOLEAN\r
+MtrrLibTypeLeftPrecedeRight (\r
+ IN MTRR_MEMORY_CACHE_TYPE Left,\r
+ IN MTRR_MEMORY_CACHE_TYPE Right\r
+)\r
+{\r
+ return (BOOLEAN) (Left == CacheUncacheable || (Left == CacheWriteThrough && Right == CacheWriteBack));\r
+}\r
+\r
+\r
+/**\r
+ Return whether the type of the specified range can precede the specified type.\r
+\r
+ @param Ranges Memory range array holding memory type settings for all\r
+ the memory address.\r
+ @param RangeCount Count of memory ranges.\r
+ @param Type Type to check precedence.\r
+ @param SubBase Base address of the specified range.\r
+ @param SubLength Length of the specified range.\r
+\r
+ @retval TRUE The type of the specified range can precede the Type.\r
+ @retval FALSE The type of the specified range cannot precede the Type.\r
+ So the subtraction is not applicable.\r
+**/\r
+BOOLEAN\r
+MtrrLibSubstractable (\r
+ IN CONST MEMORY_RANGE *Ranges,\r
+ IN UINT32 RangeCount,\r
+ IN MTRR_MEMORY_CACHE_TYPE Type,\r
+ IN UINT64 SubBase,\r
+ IN UINT64 SubLength\r
+)\r
+{\r
+ UINT32 Index;\r
+ UINT64 Length;\r
+ // WT > WB\r
+ // UC > *\r
+ for (Index = 0; Index < RangeCount; Index++) {\r
+ if (Ranges[Index].BaseAddress <= SubBase && SubBase < Ranges[Index].BaseAddress + Ranges[Index].Length) {\r
+\r
+ if (Ranges[Index].BaseAddress + Ranges[Index].Length >= SubBase + SubLength) {\r
+ return MtrrLibTypeLeftPrecedeRight (Ranges[Index].Type, Type);\r
+\r
+ } else {\r
+ if (!MtrrLibTypeLeftPrecedeRight (Ranges[Index].Type, Type)) {\r
+ return FALSE;\r
+ }\r
+\r
+ Length = Ranges[Index].BaseAddress + Ranges[Index].Length - SubBase;\r
+ SubBase += Length;\r
+ SubLength -= Length;\r
+ }\r
+ }\r
+ }\r
+\r
+ ASSERT (FALSE);\r
+ return FALSE;\r
+}\r
+\r
+/**\r
+ Return the number of required variable MTRRs to cover the specified range.\r
+\r
+ The routine considers subtraction in the both side of the range to find out\r
+ the most optimal solution (which uses the least MTRRs).\r
+\r
+ @param Ranges Array holding memory type settings of all memory\r
+ address.\r
+ @param RangeCount Count of memory ranges.\r
+ @param VariableMtrr Array holding allocated variable MTRRs.\r
+ @param VariableMtrrCount Count of allocated variable MTRRs.\r
+ @param BaseAddress Base address of the specified range.\r
+ @param Length Length of the specified range.\r
+ @param Type MTRR type of the specified range.\r
+ @param Alignment0 Alignment of 0.\r
+ @param SubLeft Return the count of left subtraction.\r
+ @param SubRight Return the count of right subtraction.\r
+\r
+ @return Number of required variable MTRRs.\r
+**/\r
+UINT32\r
+MtrrLibGetMtrrNumber (\r
+ IN CONST MEMORY_RANGE *Ranges,\r
+ IN UINT32 RangeCount,\r
+ IN CONST VARIABLE_MTRR *VariableMtrr,\r
+ IN UINT32 VariableMtrrCount,\r
+ IN UINT64 BaseAddress,\r
+ IN UINT64 Length,\r
+ IN MTRR_MEMORY_CACHE_TYPE Type,\r
+ IN UINT64 Alignment0,\r
+ OUT UINT32 *SubLeft, // subtractive from BaseAddress to get more aligned address, to save MTRR\r
+ OUT UINT32 *SubRight // subtractive from BaseAddress + Length, to save MTRR\r
+ )\r
+{\r
+ UINT64 Alignment;\r
+ UINT32 LeastLeftMtrrNumber;\r
+ UINT32 MiddleMtrrNumber;\r
+ UINT32 LeastRightMtrrNumber;\r
+ UINT32 CurrentMtrrNumber;\r
+ UINT32 SubtractiveCount;\r
+ UINT32 SubtractiveMtrrNumber;\r
+ UINT32 LeastSubtractiveMtrrNumber;\r
+ UINT64 SubtractiveBaseAddress;\r
+ UINT64 SubtractiveLength;\r
+ UINT64 BaseAlignment;\r
+ UINT32 Index;\r
+\r
+ *SubLeft = 0;\r
+ *SubRight = 0;\r
+ LeastSubtractiveMtrrNumber = 0;\r
+ BaseAlignment = 0;\r
+\r
+ //\r
+ // Get the optimal left subtraction solution.\r
+ //\r
+ if (BaseAddress != 0) {\r
+ SubtractiveBaseAddress = 0;\r
+ SubtractiveLength = 0;\r
+ //\r
+ // Get the MTRR number needed without left subtraction.\r
+ //\r
+ LeastLeftMtrrNumber = MtrrLibGetPositiveMtrrNumber (BaseAddress, Length, Alignment0);\r