✎ soc:2008:memsearch - Etherboot/gPXE Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

===== 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;
    }

Trace: • week7 • week4 • stefanha • week10 • week10 • week12 • aoebootprepdebianetch • journal • week2

Navigation

Search

Toolbox

QR Code