Summer of Code Sample Interview Exercise

This is the question that was generally given as the first (and easiest) of several programming exercises during our interviews for Google Summer of Code 2008. It requires applicants to demonstrate the ability to write in C code, including the use of pointers.

Question

Implement the following function:

  /**
   * Search memory for a 32-bit pattern match on a 32-bit boundary
   *
   * @v start             Start address of region to search
   * @v len               Length of region, in bytes
   * @v pattern           Pattern to search for
   * @v mask              Mask of which bits in the pattern we care about
   * @ret found           First address at which pattern is found
   *
   *
   * The mask is used to indicate that we care about only part of the
   * pattern matching.  For example, suppose we wanted to search the
   * region for words of the form
   *
   *   0xabcdXXXX
   *
   * where X indicates that we don't care about that digit (i.e. that we
   * would want to match on 0xabcd0000, or 0xabcd1234, or 0xabcdffff,
   * etc.).  We would then call memsearch() as
   *
   *   memsearch ( start, len, 0xabcd0000, 0xffff0000 );
   */
  uint32_t * memsearch ( uint32_t *start, size_t len,
                         uint32_t pattern, uint32_t mask ) {
  
  }

Sample answer

This is one valid answer to the question. There are many possible answers. We accepted any answer that was functionally correct and sensibly laid out.

  uint32_t * memsearch ( uint32_t *start, size_t len,
                         uint32_t pattern, uint32_t mask ) {
      uint32_t *test;
  
      assert ( ( len % sizeof ( *test ) ) == 0 );
  
      for ( test = start ; len ; test++, len -= sizeof ( *test ) ) {
          if ( ( ( *test ^ pattern ) & mask ) == 0 )
              return test;
      }
  
      return NULL;
  }

Navigation

* [[:start|Home]] * [[:about|About our Project]] * [[:download|Download]] * [[:screenshots|Screenshots]] * Documentation * [[:howtos|HowTo Guides]] * [[:appnotes|Application Notes]] * [[:faq:|FAQs]] * [[:doc|General Doc]] * [[:talks|Videos, Talks, and Papers]] * [[:hardwareissues|Hardware Issues]] * [[:mailinglists|Mailing lists]] * [[http://support.etherboot.org/|Bugtracker]] * [[:contributing|Contributing]] * [[:editing_permission|Wiki Edit Permission]] * [[:wiki:syntax|Wiki Syntax]] * [[:contact|Contact]] * [[:relatedlinks|Related Links]] * [[:commerciallinks|Commercial Links]] * [[:acknowledgements|Acknowledgements]] * [[:logos|Logo Art]]

QR Code
QR Code soc:2008:memsearch (generated for current page)