It can be seen that, while looping inside encode_symbol() and decode_symbol(), as soon as the conditions high<Half and low>=Half are not met, they won't be met again. Moreover, a "bits plus follow" call is needed only once at the beginning; then "output bit" is enough. Here is the encode method structure changed:

do
{
   if (high<Half)
   {
      bit plus follow 0;
   }
   else if (low>=Half)
   {
      bit plus follow 1;

      low  -= Half;
      high -= Half;
   }
   else
      break;

   for (;;)
   {
      low  = 2*low;
      high = 2*high+1;

      if (high<Half)
      {
         output bit 0;
      }
      else if (low>=Half)
      {
         output bit 1;

         low  -= Half;
         high -= Half;
      }
      else
         break;
   }
}
while (false);

while (low>=First_qtr && high<Third_qtr)
{
   bits_to_follow++;
   low  = 2 * (low - First_qtr);    // Subtract offset to middle
   high = 2 * (high - First_qtr) + 1;
}

Because only 16 bits of low and high variables are used, these variables are substituted by the combined low_high one.

low_high = low + ((~high) << 16);

Variable high binary negation makes the next optimizations possible: As soon as ~X is equal to -X - 1, ~((~X) << 1) stands for 2 * X + 1. Then,

low  = 2*low;
high = 2*high+1;

can be substituted by just:

low_high <<= 1;

The cycle with checking

while (low>=First_qtr && high<Third_qtr)

can be reduced to (taking into account that conditions high<Half and low>=Half are met):

//while (low>=First_qtr && high<Third_qtr)
unsigned long buf = ~low_high;
if (!(buf & 0x40004000))
{
   do
   {
      bits_to_follow++;
      //low = 2 * (low - First_qtr);    // Subtract offset to
                                        // middle
      //high = 2 * (high - First_qtr) + 1;
      buf = (buf << 1) + 1 + (First_qtr << 1) -
            (First_qtr << 17);
   }
   while (!(buf & 0x40004000));
   low_high = ~buf;
}

Flushing bits to follow can be optimized as well. The flush_bits_to_follow helper is introduced; it simply puts the required amount of one or zero bits to the output:

void bit_plus_follow_0()
{
   output_bit_0();    /* Output the bit.          */
   while (bits_to_follow>0) {
      buffer >>= 1; buffer |= 0x80;
                      /* Put bit in top of buffer.*/
      if (--bits_to_go==0) {
                       /* Output buffer if it is   */
         flush_bits_to_follow(255);
         return;
      }
      bits_to_follow--;
                      /* opposite bits. Set       */
   }                  /* bits_to_follow to zero.  */
}

void output_bit_0()
{
   buffer >>= 1;    //if (bit) buffer |= 0x80;
      /* Put bit in top of buffer.*/
   if (--bits_to_go==0) {
      /* Output buffer if it is   */
      PutByte_(buffer);
      /* now full.                */
      bits_to_go = 8;
   }
}

void flush_bits_to_follow(int buffer_)
{
   for (;;)
   {
      PutByte_(buffer);    /* now full.                */
      buffer = buffer_;
      if (bits_to_follow <= 8)
         break;
      bits_to_follow -= 8;
   }
   bits_to_go = 9 - bits_to_follow;
   bits_to_follow = 0;
}

However, there is a drawback concerned with code value buffer capacity limitation. It can be fixed by changing the way conditions are checked. For maximal code value buffer size (32 bits for IA32 in this example), the algorithm encoding loop body fragment,

for (;;)
{
   if (high < Half)
   {
      bit plus follow 0;
   }
   else if (low >= Half)
   {
      bit plus follow 1;

      low  -= Half;
      high -= Half;
   }
   else
      break;

   low  = 2*low;
   high = 2*high+1;
}

with introduction of the special flags,

long half_flags = ~(low | not_high);

can be changed to:

int shift = num_clear_bits(half_flags);
if (shift != 0)
{
   bit_plus_follow(low & Half);
   // This loop can be definitely optimized
   unsigned long flag = Half;
   for (int i = shift; --i > 0;)
   {
      flag >>= 1;
      output_bit(low & flag);
   }
   low <<= shift;
   not_high <<= shift;
}