Collating bits from a byte source

• US 6,016,524 A
• Filed: 04/24/1998
• Issued: 01/18/2000
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: 8X8, Inc.
• Original Assignee: 8X8, Inc.
• Inventors: Kleck, James
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/066,248
• Time in Patent Office: 634 Days
• Field of Search: 710/62, 710/65, 710/68, 710/72, 712/898, 707/6
• US Class Current: 710/65
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

A bit collation method is disclosed which requires a substantially fewer number of clock cycles than the prior art method in separating the bits in a source of bytes and collating them by bit position. A static look-up table is used to spread out the bits in a byte being collated. The look-up table enables simultaneous collation of all bits in a byte using only five clock cycles.

Claims

1. A method for collating a bit-group having a plurality of bits, comprising:

generating a bit-pattern corresponding to the plurality of bits in the bit-group, the bit pattern including bit-segments equal in number to the plurality of bits in the bit-group, each of the bit-segments having a first number of bit positions, and one bit position in each of the bit-segments occupied by a corresponding bit in the bit-group, all other positions in each of the bit-segments occupied by a selected bit value; and

combining the bit-pattern with contents of an accumulation register, placing a result thereof in the accumulation register.

2. The method of claim 1, wherein the one position in each of the bit-segments in the bit-pattern is the least significant bit position in each of the bit-segments in the bit-pattern.

3. The method of claim 2, wherein the accumulation register includes bit-segments equal in number to the plurality of bits in the bit-group, each of the bit-segments in the accumulation register having a second number of bit positions.

4. The method of claim 3, further comprising:

clearing a most significant bit position in each of the bit-segments in the accumulation register before combining the bit-pattern with the contents of the accumulation register; and

shifting left the contents of the accumulation register by one bit position after clearing the most significant bits.

5. The method of claim 4, wherein the selected bit value is 0.

6. The method of claim 5, wherein combining includes a logical OR operation.

7. The method of claim 6, fuirther comprising comparing contents of each of the bit-segments with a selected pattern of bits after combining the bit-pattern with the contents of the accumulation register.

8. The method of claim 7, wherein each of the first and second number of bit positions are equal to a number of bits in the selected pattern of bits.

9. The method of claim 7, wherein each of the first and second number of bit positions are greater than a number of bits in the selected pattern of bits.

10. The method of claim 5, wherein combining includes a logical ADD operation.

11. An apparatus for collating a bit-group having a plurality of bits, comprising:

means for generating a bit-pattern corresponding to the plurality of bits in the bit-group, the bit pattern including bit-segments equal in number to the plurality of bits in the bit-group, each of the bit-segments having a first number of bit positions, and one bit position in each of the bit-segments occupied by a corresponding bit in the bit-group, all other positions in each of the bit-segments occupied by a selected bit value; and

means for combining the bit-pattern with contents of an accumulation register, and placing a result thereof in the accumulation register.

12. An apparatus for collating a bit-group having a plurality of bits, comprising a processor configured and arranged to generate a bit-pattern corresponding to the plurality of bits in the bit-group, the bit pattern including bit-segments equal in number to the plurality of bits in the bit-group, each of the bit-segments having a first number of bit positions, and one bit position in each of the bit-segments occupied by a corresponding bit in the bit-group, all other positions in each of the bit-segments occupied by a selected bit value, and combine the bit-pattern with contents of an accumulation register, and placing a result thereof in the accumulation register.

13. A method for locating a selected bit pattern in an input stream of bytes, the bit pattern sought in bits having a common position in the input bytes, comprising the steps of:

generating a multi-segment bit pattern corresponding to an input byte, the multi-segment bit pattern including a plurality of bit-segments, each having one bit position with a value indicated by a corresponding bit in the input byte, and all other bit positions in the bit-segments having a selected bit value;

generating a new value for an accumulation register based on the multi-segment bit pattern and a present value of the accumulation register, the accumulation register having portions corresponding to bit positions in the input bytes;

repeating the steps of generating the multi-segment bit pattern and generating the new value for the accumulation register until a selected number of input bytes have been processed; and

locating the selected bit pattern in the accumulation register.

14. The method of claim 13, wherein the step of generating a new value for the accumulation register based on the bit pattern and a present value of the accumulation register includes the step of:

performing a logical-OR operation on the bit pattern and the accumulation register; and

shifting left one bit contents of the accumulation register.

15. The method of claim 14, wherein:

values of bits of the input byte are stored as corresponding least significant bits of bit-segments of the bit pattern;

the step of generating a new value for the accumulation register further includes the step of clearing least significant bits of the portions of the accumulation register.

16. The method of claim 15, wherein the selected value of the other bits in the multi-segment bit pattern is logical 0.

17. The method of claim 13, wherein a number of bits in each of the bit-segments and each portion of the accumulation register and the selected number of input bytes are equal to the number of bits in the selected bit pattern.

18. The method of claim 13, wherein the selected bit pattern is a service channel and the input bytes include an audio channel and a video channel.

19. An apparatus for locating a selected bit pattern in an input stream of bytes, the bit pattern sought in bits having a common position in the input bytes, comprising:

means for generating a multi-segment bit pattern corresponding to an input byte, the multi-segment bit pattern including a plurality of bit-segments, each having one bit position with a value indicated by a corresponding bit in the input byte, and all other bit positions in the bit-segments having a selected bit value;

means for generating a new value for an accumulation register based on the multi-segment bit pattern and a present value of the accumulation register, the accumulation register having portions corresponding to bit positions in the input bytes;

means for continuing to generate the multi-segment bit pattern and generate the new value for the accumulation register until a selected number of input bytes have been processed; and

means for locating the selected bit pattern in one of the portions of the accumulation register.

20. The apparatus of claim 19, further including:

means for performing a logical-OR operation on the bit pattern and the accumulation register; and

means for shifting left one bit contents of the accumulation register.

21. The apparatus of claim 20, wherein:

values of bits of the input byte are stored as corresponding least significant bits of bit-segments of the bit pattern; and

further including means for clearing least significant bits of the portions of the accumulation register.

22. The apparatus of claim 21, wherein the selected value of the other bits in the multi-segment bit pattern is logical 0.

23. The apparatus of claim 19, wherein a number of bits in each of the bit-segments and each portion of the accumulation register and the selected number of input bytes are equal to the number of bits in the selected bit pattern.

24. The apparatus of claim 19, wherein the selected bit pattern is a service channel and the input bytes include an audio channel and a video channel.

25. An system for locating a selected bit pattern in an input stream of bytes, the bit pattern sought in bits having a common position in the input bytes, comprising a processor configured and arranged to (a) generate a multi-segment bit pattern corresponding to an input byte, the multi-segment bit pattern including a plurality of bit-segments, each having one bit position with a value indicated by a corresponding bit in the input byte, and all other bit positions in the bit-segments having a selected bit value, (b) generate a new value for an accumulation register based on the multi-segment bit pattern and a present value of the accumulation register, the accumulation register having portions corresponding to bit positions in the input bytes, (c) continue to generate the multi-segment bit pattern and generate the new value for the accumulation register until a selected number of input bytes have been processed, and (d) locate the selected bit pattern in the accumulation register.