Check in a branch with a major redesign on how entropy polling is performed.

Combine the fast and slow polls, into a single poll() operation.

Instead of being given a buffer to write output into, the EntropySource is
passed an Entropy_Accumulator. This handles the RLE encoding that xor_into_buf
used to do. It also contains a cached I/O buffer so entropy sources do not
individually need to allocate memory for that with each poll. When data
is added to the accumulator, the source specifies an estimate of the number
of bits of entropy per byte, as a double. This is tracked in the accumulator.
Once the estimated entropy hits a target (set by the constructor), the
accumulator's member function predicate polling_goal_achieved flips to true.
This signals to the PRNG that it can stop performing polling on sources,
also polls that take a long time periodically check this flag and return
immediately.

The Win32 and BeOS entropy sources have been updated, but blindly; testing
is needed.

The test_es example program has been modified: now it polls twice and outputs
the XOR of the two collected results. That helps show if the output is consistent
across polls (not a good thing). I have noticed on the Unix entropy source,
occasionally there are many 0x00 bytes in the output, which is not optimal.
This also needs to be investigated.

The RLE is not actually RLE anymore. It works well for non-random inputs
(ASCII text, etc), but I noticed that when /dev/random output was fed into
it, the output buffer would end up being RR01RR01RR01 where RR is a random
byte and 00 is the byte count.

The buffer sizing also needs to be examined carefully. It might be useful
to choose a prime number for the size to XOR stuff into, to help ensure an
even distribution of entropy across the entire buffer space. Or: feed it
all into a hash function?

This change should (perhaps with further modifications) help WRT the
concerns Zack W raised about the RNG on the monotone-dev list.

2 files changed, 79 insertions, 94 deletions

diff --git a/src/entropy/win32_stats/es_win32.cpp b/src/entropy/win32_stats/es_win32.cpp
index a529ccc1a..0c17f7b02 100644
--- a/src/entropy/win32_stats/es_win32.cpp
+++ b/src/entropy/win32_stats/es_win32.cpp
@@ -1,43 +1,69 @@
 /**
 * Win32 EntropySource Source File
-* (C) 1999-2008 Jack Lloyd
+* (C) 1999-2009 Jack Lloyd
 */
 
 #include <botan/es_win32.h>
-#include <botan/xor_buf.h>
 #include <windows.h>
 #include <tlhelp32.h>
 
 namespace Botan {
 
 /**
-* Win32 slow poll using Tooltip32
+* Win32 poll using stats functions including Tooltip32
 */
-u32bit Win32_EntropySource::slow_poll(byte buf[], u32bit length)
+void Win32_EntropySource::poll(Entropy_Accumulator& accum)
    {
-   if(length == 0)
-      return 0;
+   /*
+   First query a bunch of basic statistical stuff, though
+   don't count it for much in terms of contributed entropy.
+   */
+   accum.add(GetTickCount(), 0);
+   accum.add(GetMessagePos(), 0);
+   accum.add(GetMessageTime(), 0);
+   accum.add(GetInputState(), 0);
+   accum.add(GetCurrentProcessId(), 0);
+   accum.add(GetCurrentThreadId() 0);
 
-   const u32bit MAX_ITEMS = length / 4;
+   SYSTEM_INFO sys_info;
+   GetSystemInfo(&sys_info);
+   accum.add(sys_info, 1);
+
+   MEMORYSTATUS mem_info;
+   GlobalMemoryStatus(&mem_info);
+   accum.add(mem_info, 1);
+
+   POINT point;
+   GetCursorPos(&point);
+   accum.add(point, 1);
+
+   GetCaretPos(&point);
+   accum.add(point, 1);
+
+   LARGE_INTEGER perf_counter;
+   QueryPerformanceCounter(&perf_counter);
+   accum.add(perf_count, 0);
 
-   u32bit buf_i = 0;
+   /*
+   Now use the Tooltip library to iterate throug various objects on
+   the system, including processes, threads, and heap objects.
+   */
 
    HANDLE snapshot = CreateToolhelp32Snapshot(TH32CS_SNAPALL, 0);
 
 #define TOOLHELP32_ITER(DATA_TYPE, FUNC_FIRST, FUNC_NEXT) \
-   {                                                      \
-   u32bit items = 0;                                      \
-   DATA_TYPE info;                                        \
-   info.dwSize = sizeof(DATA_TYPE);                       \
-   if(FUNC_FIRST(snapshot, &info))                        \
+   if(!accum.polling_goal_achieved())                     \
       {                                                   \
-      do                                                  \
+      DATA_TYPE info;                                     \
+      info.dwSize = sizeof(DATA_TYPE);                    \
+      if(FUNC_FIRST(snapshot, &info))                     \
          {                                                \
-         if(items++ > MAX_ITEMS) break;                   \
-         buf_i = xor_into_buf(buf, buf_i, length, info);  \
-         } while(FUNC_NEXT(snapshot, &info));             \
-      }                                                   \
-   }
+         do                                               \
+            {                                             \
+            accum.add(info, 1);                           \
+            } while(FUNC_NEXT(snapshot, &info));          \
+         }                                                \
+      }
 
    TOOLHELP32_ITER(MODULEENTRY32, Module32First, Module32Next);
    TOOLHELP32_ITER(PROCESSENTRY32, Process32First, Process32Next);
@@ -45,85 +71,46 @@ u32bit Win32_EntropySource::slow_poll(byte buf[], u32bit length)
 
 #undef TOOLHELP32_ITER
 
-   u32bit heap_lists_found = 0;
-   HEAPLIST32 heap_list;
-   heap_list.dwSize = sizeof(HEAPLIST32);
-
-   const u32bit HEAP_LISTS_MAX = 32;
-   const u32bit HEAP_OBJS_PER_LIST = 128;
-   if(Heap32ListFirst(snapshot, &heap_list))
+   if(!accum.polling_goal_achieved())
       {
-      do
-         {
-         buf_i = xor_into_buf(buf, buf_i, length, heap_list);
+      u32bit heap_lists_found = 0;
+      HEAPLIST32 heap_list;
+      heap_list.dwSize = sizeof(HEAPLIST32);
 
-         if(heap_lists_found++ > HEAP_LISTS_MAX)
-            break;
+      const u32bit HEAP_LISTS_MAX = 32;
+      const u32bit HEAP_OBJS_PER_LIST = 128;
 
-         u32bit heap_objs_found = 0;
-         HEAPENTRY32 heap_entry;
-         heap_entry.dwSize = sizeof(HEAPENTRY32);
-         if(Heap32First(&heap_entry, heap_list.th32ProcessID,
-                                     heap_list.th32HeapID))
+      if(Heap32ListFirst(snapshot, &heap_list))
+         {
+         do
             {
-            do
+            accum.add(heap_list, 1);
+
+            if(++heap_lists_found > HEAP_LISTS_MAX)
+               break;
+
+            u32bit heap_objs_found = 0;
+            HEAPENTRY32 heap_entry;
+            heap_entry.dwSize = sizeof(HEAPENTRY32);
+            if(Heap32First(&heap_entry, heap_list.th32ProcessID,
+                           heap_list.th32HeapID))
                {
-               if(heap_objs_found++ > HEAP_OBJS_PER_LIST)
-                  break;
-               buf_i = xor_into_buf(buf, buf_i, length, heap_entry);
-               } while(Heap32Next(&heap_entry));
-            }
-         } while(Heap32ListNext(snapshot, &heap_list));
+               do
+                  {
+                  if(heap_objs_found++ > HEAP_OBJS_PER_LIST)
+                     break;
+                  accum.add(heap_entry, 1);
+                  } while(Heap32Next(&heap_entry));
+               }
+
+            if(accum.polling_goal_achieved())
+               break;
+
+            } while(Heap32ListNext(snapshot, &heap_list));
+         }
       }
 
    CloseHandle(snapshot);
-
-   return length;
-   }
-
-/**
-* Win32 fast poll
-*/
-u32bit Win32_EntropySource::fast_poll(byte buf[], u32bit length)
-   {
-   if(length == 0)
-      return 0;
-   length = std::min<u32bit>(length, 32);
-
-   u32bit buf_i = 0;
-
-   u32bit stats[] = {
-      GetTickCount(),
-      GetMessagePos(),
-      GetMessageTime(),
-      GetInputState(),
-      GetCurrentProcessId(),
-      GetCurrentThreadId()
-   };
-
-   for(u32bit i = 0; i != sizeof(stats) / sizeof(stats[0]); ++i)
-      buf_i = xor_into_buf(buf, buf_i, length, stats[i]);
-
-   SYSTEM_INFO sys_info;
-   GetSystemInfo(&sys_info);
-   buf_i = xor_into_buf(buf, buf_i, length, sys_info);
-
-   MEMORYSTATUS mem_info;
-   GlobalMemoryStatus(&mem_info);
-   buf_i = xor_into_buf(buf, buf_i, length, mem_info);
-
-   POINT point;
-   GetCursorPos(&point);
-   buf_i = xor_into_buf(buf, buf_i, length, point);
-
-   GetCaretPos(&point);
-   buf_i = xor_into_buf(buf, buf_i, length, point);
-
-   LARGE_INTEGER perf_counter;
-   QueryPerformanceCounter(&perf_counter);
-   buf_i = xor_into_buf(buf, buf_i, length, perf_counter);
-
-   return length;
    }
 
 }
diff --git a/src/entropy/win32_stats/es_win32.h b/src/entropy/win32_stats/es_win32.h
index 3124bd414..06e3b88cc 100644
--- a/src/entropy/win32_stats/es_win32.h
+++ b/src/entropy/win32_stats/es_win32.h
@@ -1,6 +1,6 @@
 /**
 * Win32 EntropySource Header File
-* (C) 1999-2008 Jack Lloyd
+* (C) 1999-2009 Jack Lloyd
 */
 
 #ifndef BOTAN_ENTROPY_SRC_WIN32_H__
@@ -17,9 +17,7 @@ class BOTAN_DLL Win32_EntropySource : public EntropySource
    {
    public:
       std::string name() const { return "Win32 Statistics"; }
-
-      u32bit fast_poll(byte buf[], u32bit length);
-      u32bit slow_poll(byte buf[], u32bit length);
+      void poll(Entropy_Accumulator& accum);
    };
 
 }