Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Speed up an Bitsearch Function

Posted on 2005-04-07
35
Medium Priority
?
310 Views
Last Modified: 2010-04-01
Hello,

I have following problem: I have an Function to read Bits from an Buffer And to search an value 0x00001 (0x00,0x00,0x01):.
//-------------------------------------------

//-----------main Routine, that iis slow-----
//-------------------------------------------
bool  CMPEGBitstream::next_start_code()
{
      Flush_Buffer(m_BitsLeft & 7);

      while (Show_Bits(24) != 1 && m_Fault_Flag<CRITICAL_ERROR_LEVEL)
            Flush_Buffer(8);
      return true;
}
//--------------------------------------------
//---------------Sub functions----------------
//--------------------------------------------
unsigned int CMPEGBitstream::Show_Bits(int N)
{
      return (m_CurrentBfr >> (32 - N));
}

void CMPEGBitstream::Flush_Buffer(unsigned int N)
{
      m_BitsLeft -= N;
      m_CurrentBfr <<= N;

      while( m_BitsLeft<=24 ) {
            if(m_SystemStream_Flag)
                  if(m_Rdptr>=m_Rdmax ) Next_Packet();
            if (m_Rdptr >= m_Rdbfr+BUFFER_SIZE) Fill_Buffer();
            m_CurrentBfr |= *(m_Rdptr++) << (24 - m_BitsLeft);
            m_BitsLeft+=8;
      }
}

But this Funktion is realy slow. Now I read some papers and I think that this Function is to heavy.
It need to search an 0x00001 (Three Bytes 0x00 0x00 0x01) in the Buffer. But this Funktion search by bit.
It makes an 24 bit Integer and search for 1.

But I think it can better search by byte. In my mind, this will increase the function 8 times. But Iam to
stupid to make this.

Anyone here who can give me an tip or solution?

Ocrana
0
Comment
Question by:Ocrana
  • 13
  • 5
  • 3
  • +3
27 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 2000 total points
ID: 13731220
If I get you right, you're looking for what is known as 'packet_start_code_prefix'. Since you have already processed the previous packets, you should know it's 'PES payload size', thus making it easy to calculate the start address of the next packet (and it's prefix) by adding the payload size like

new_packet_start_addr = old_packet_start_addr + old_packet_header_size + old_packet_payload_size;

The packet's header size will depend on the stream type, padding etc.

No need to search for a start code prefix at all...
0
 
LVL 86

Expert Comment

by:jkr
ID: 13731229
Oh, speaking of padding, you might have to add that to the above formula also, again depending on the stream type.
0
 
LVL 86

Expert Comment

by:jkr
ID: 13731445
BTW - if you want to take a look a t a working implementation, check out http://members.cox.net/beyeler/bbmpeg.html ("bbMPEG's Home Page")
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 22

Expert Comment

by:grg99
ID: 13732748
Your code is grabbing a byte at a time it seems, not a bit at a time.  

If you can use jkr's suggestion, that's obviously the faster way to go.

Otherwise, if the bytes your looking for are byte-aligned, you could just scan the whole buffer for 16 bits of zeroes, then look for a 01 byte just before it (or after, depending on order).  Looking for 16-bits of zero can be very fast.

0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13737006
> But this Funktion is realy slow. Now I read some papers and I think that this Function is to heavy. It need to search an 0x00001 (Three Bytes 0x00 0x00 0x01) in the Buffer. But this Funktion search by bit. It makes an 24 bit Integer and search for 1.

> But I think it can better search by byte. In my mind, this will increase the function 8 times. But Iam to stupid to make this.

The best way to speed things up is to use jkr's solution, if it's viable (I'm no expert in mpeg file formats).  Seeking straight to wherever you need to go is always going to be faster than parsing everything in between where you are and where you want to go.

If you can't do it that way, there are some ways to speed up your function.  For one thing, the Show_Bits(N) function slows things down when we know we're looking at the top 24 bits of the buffer.  Also, the buffer is only flushed 8 bits at a time when it's possible to to it faster.

This version cuts out all calls to Show_Bits, and reduces the number of calls to Flush_Buffer to somewhere between 1/2 and 1/4 the previous number of calls.  I don't think it's possible to speed up Flush_Buffer without violating some kind of important buffering semantics.

bool  CMPEGBitstream::next_start_code()
{
     Flush_Buffer(m_BitsLeft & 7);

     do {
          if (m_CurrentBfr & 0xffffff00 == 0x00000100) {
               return true;
          }
          if (m_CurrentBfr & 0x00ffffff == 0x00000001) {
               Flush_Buffer(8);
               return true;
          }
          if (m_CurrentBfr & 0x000000FF != 0) {
              Flush_Buffer(32);  // we know no part of the the 000001 token is in m_CurrentBfr
          } else {
              Flush_Buffer(16); // bottom byte is 00, which might be part of the 000001 token.
          }
     } while (m_Fault_Flag<CRITICAL_ERROR_LEVEL);
     return true;
}
0
 
LVL 86

Expert Comment

by:jkr
ID: 13737085
>>The best way to speed things up is to use jkr's solution, if it's viable

Actually, that's the way Packetized Elementary Streams and decoders work - no MPEG player is able to do a real time search through the stream to find a packet start code (imagine a throughput of up to 1MB video data for e.g. MPEG2 in DVD quality, not to speak of audio). Furthermore, there's the time that's needed to uncompress and decode the payload.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13737114
Darnit, my code won't work.  It assumes m_BitsLeft is 32.  I am only allowed to assume that m_BitsLeft >=24.

bool  CMPEGBitstream::next_start_code()
{
     Flush_Buffer(m_BitsLeft & 7);

     do {
          switch ((m_CurrentBuf & 0x0000ff00) >> 8) {
              case 0x01:
                     if (m_CurrentBfr & 0xffffff00 == 0x00000100) {
                          return true;
                     } else {
                          // no part of 000001 is in top 24 bits of m_CurrentBfr
                          Flush_Buffer(24);
                     }
              break;
          case 0x00:
              Flush_Buffer(8);
              break;
          default:
              // no part of 000001 is in top 24 bits of m_CurrentBfr
              Flush_Buffer(24);
          }
     } while (m_Fault_Flag<CRITICAL_ERROR_LEVEL);
     return true;
}
0
 
LVL 22

Expert Comment

by:grg99
ID: 13737245
> no MPEG player is able to do a real time search through the stream to find a packet start code

yeahbut sometimes you come in in the middle of a playing stream  and have to find the next marker in order to get resynched-- or you may have a bad mpeg file and have to resync,  or maybe a packet never comes in and you have to resync.

I agree it's a good idea to avoid searching if possible.  Sometimes it's not possible./
0
 

Author Comment

by:Ocrana
ID: 13737274
jkr: This class is for an MpegScanner not for an Player. So i ignore video and audio data, my interseting is only in the headers.

NovaDenizen: You mean, the second code part works?

0
 
LVL 86

Expert Comment

by:jkr
ID: 13737668
>>my interseting is only in the headers.

HAve you checked the sample I linked above? Even if you do not want to play the stream, it's kinda more effective to directly read the headers from where they're described to be...
0
 
LVL 86

Expert Comment

by:jkr
ID: 13737814
>>sometimes you come in in the middle of a playing stream  and have to find the next marker in order to get resynched

Um, not really - you'll always get 2048-byte sized packs that start witha pack header of a given length, so finding the 1st pack is

packet_start_addr = pack_start_addr + pack_header_length;
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13739301
Ocrana:  I think my second function will have the same result as your original, and I think it will be faster than your original.  However, if most of the time is spent in Flush_Buffer my speedups might not be very significant.
0
 

Author Comment

by:Ocrana
ID: 13805243
Hello,

I have tried now much with your suggestions. But no of them will increaset he speed.

Ocrana
0
 
LVL 86

Expert Comment

by:jkr
ID: 13810384
>>I have tried now much with your suggestions.

Dunno whether somone has mentioned that already, but have you taken a look at http://members.cox.net/beyeler/bbmpeg.html ? (HINT: You'll find WORKING code there)
0
 

Author Comment

by:Ocrana
ID: 13811205
Hi,

I have take a look into bbmpeg but this is an encoder and not an decoder. In an encoder it is easier to handle this cause there I have a fixed structure and I have the control to write that what I want. But in case of ready encoded mpeg files, it is complicated to use a fixed position cause I have around 7 mpegs that have no fixed sizes between the packet headers. So to use a stored size is not the right choice.

Ocrana
0
 
LVL 86

Expert Comment

by:jkr
ID: 14512239
Hm, to some extent I object a deletion.
0
 
LVL 14

Expert Comment

by:wayside
ID: 15645308
No comment has been added to this question in more than 21 days, so it is now classified as abandoned..
I will leave the following recommendation for this question in the Cleanup topic area:

PAQ - Refund

Any objections should be posted here in the next 4 days. After that time, the question will be closed.

wayside
EE Cleanup Volunteer
0
 
LVL 86

Expert Comment

by:jkr
ID: 15645582
Um, tend to object - I was pointing the direction quite some times, and believe me, that's part of my daily work. The comment #13731220 still stands.
0
 
LVL 14

Expert Comment

by:wayside
ID: 15645716
Hmmm, well, I don't know much about mpeg processing, but OP explicitly said "I have around 7 mpegs that have no fixed sizes between the packet headers. So to use a stored size is not the right choice." which I took to mean that he did not find that your solution worked for him. I thought there was useful info in here, though, so I recommended to PAQ it.

If you believe the OP doesn't know what he is talking about and your solution should in fact have worked for him, I have no objection if the mod overrides me.
0
 
LVL 86

Expert Comment

by:jkr
ID: 15645748
>>So to use a stored size is not the right choice

Yes, you have to dynamically calculate that from each header consecutively, but all the info is there. Yet I remained unheard ;o)
0
 
LVL 14

Expert Comment

by:wayside
ID: 15645769
Ok, you convinced me.

Change recommendation to:

Accept: jkr
0
 

Author Comment

by:Ocrana
ID: 15698093
It is really amazing what type of answers the Admins forced as accpeted.  jkr answer was not that what I asked and so in this case wrong.  I worked 4 month now on improve the bitsearch functon and it is not an easy handwipe jkr wrote. jkr's solution was defintly wrong (reports wrong data) and the free software he sent was one of the oldest and worst encoders available.

So my lovely admin, you make an fault and so you steal my money. Not an good part of your work! And not part of an site that called itself as "expert".

Ocrana
0
 
LVL 86

Expert Comment

by:jkr
ID: 15698455
*shrug*

It works for a *lot* of other people at least, so I am not really bothered...
0
 

Author Comment

by:Ocrana
ID: 15699645
Hello admin,

the 500 Points were not credited back to my account, I think so that the "expert" get the 500 Points. So the result is, you forced an wrong answer and took my money.  I set the Points very high to get an real expert answer. THis points are now gone (Points I buy here) for something I do not get.
Is this your definition of "expert" knowledge?

Hello jkr,

mpeg is an real heavy thing. There are two parts of mpeg. Decoding and encoding. Your message redards to encoding. Encoding is an allways straight line process. The coder can predefine the workflow. But you forget that decoding is an different thing. You need to handle much things while decoding. You have to check all possible encding types. Take a look to cinema craft encoder. There you will see that an global straight line thing is history.
Also I do not know why you are not able to accept that your posting is not that what I needed.  Also it is very hard to understand for me that you wrote "It works for a *lot* of people. My name is Ocrana and my question was about my problem. Do you really think that I set an high point question if i need an default answer that everyone have?

All this is really amazing and not that what I understand under the term of "expert". So admin, if you are on the run to steal my money, make it final. Get my last 190 points, give them to jkr and close my account. I do not need things like this.

Ocrana
0
 
LVL 86

Expert Comment

by:jkr
ID: 15701431
>>Your message redards to encoding. Encoding is an allways straight line process.

I haven't been talking about 'encoding' at all.

>>Also it is very hard to understand for me that you wrote "It works for a *lot* of people.

That should have been "It works for all who know Packtized Elementary Streams"

Goodspeed. And be sure to get your basics right before claiming stupid things in public.
0
 
LVL 86

Expert Comment

by:jkr
ID: 16226234
Careful, you are opening Pandora's box here... I still stand to my point.
0
 
LVL 20

Expert Comment

by:Venabili
ID: 16226282
Want my honest opinion? If the first recommendation was not here ( and all after this) I would post Point to jkr immediatelly.
In this case: I want to hear from everyone and whatever I decide it WILL NOT be REFUND. Because our Asker here left it to get abandoned for a second time....
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

577 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question