vectorized_string.h

Go to the documentation of this file.

/*
 * nvbio
 * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *    * Neither the name of the NVIDIA CORPORATION nor the
 *      names of its contributors may be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once

#include <nvbio/basic/types.h>
#include <nvbio/basic/vector_view.h>
#include <nvbio/basic/packedstream.h>
#include <nvbio/basic/vector_loads.h>
#include <nvbio/strings/string_traits.h>
#include <nvbio/strings/string.h>
#include <string.h>


namespace nvbio {




template <typename string_type>
struct vectorized_string
{
    typedef typename string_traits<string_type>::value_type value_type;
    
    static const uint32 VECTOR_WIDTH = 1u;  

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const string_type& string)
    {
        const uint32 rounded_length = (uint32)util::round_z( length( string ), VECTOR_WIDTH_T );
        return make_uint2( 0, rounded_length );
    }

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const string_type&  string,
        const uint32        offset,
        value_type*         vector)
    {
        // fill the vector with a simple loop
        #pragma unroll
        for (uint32 j = 0; j < VECTOR_WIDTH_T; ++j)
            vector[j] = string[offset + j];
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const string_type& string)
    {
        return range<VECTOR_WIDTH>( string );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const string_type&  string,
        const uint32        offset,
        value_type*         vector)
    {
        load<VECTOR_WIDTH>( string, offset, vector );
    }
};

template <typename string_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
uint2 vectorized_string_range(const string_type& string)
{
    return vectorized_string<string_type>::range( string );
}

template <typename string_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
void vectorized_string_load(const string_type& string, const uint32 i, typename string_traits<string_type>::value_type* vector)
{
    vectorized_string<string_type>::load( string, i, vector );
}

//
// --- const char* specialization------------------------------------------------------------------------
//

template <>
struct vectorized_string<const char*>
{
    typedef const char*                    string_type;
    typedef char                           value_type;
    typedef uint64                         index_type;

    static const uint32 VECTOR_WIDTH = maximum_vector_width<char>::VALUE; 

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const char* string)
    {
        const uint64 offset = uint64( string ) % VECTOR_WIDTH_T;
        const uint64 len    = length( string );

        const uint64 aligned_begin = util::round_i( offset,                 VECTOR_WIDTH );
        const uint64 aligned_end   = util::round_z( offset + len, VECTOR_WIDTH );

        return aligned_begin < aligned_end ?
            make_uint2( aligned_begin - offset, aligned_end - offset ) :
            make_uint2( len, len );
    }

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const char*  string,
        const uint32 offset,
        char*        vector)
    {
        const char* base_ptr = string + offset;
        vector_load<VECTOR_WIDTH_T>( base_ptr, vector );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const char* string)
    {
        return range<VECTOR_WIDTH>( string );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const char*  string,
        const uint32 offset,
        char*        vector)
    {
        load<VECTOR_WIDTH>( string, offset, vector );
    }
};

//
// --- vector_view<const T*> specialization------------------------------------------------------------------------
//

template <typename T, typename IndexType>
struct vectorized_string< vector_view<const T*,IndexType> >
{
    typedef vector_view<const T*,IndexType> string_type;
    typedef T                               value_type;
    typedef IndexType                       index_type;

    static const uint32 VECTOR_WIDTH = maximum_vector_width<T>::VALUE; 

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const string_type& string)
    {
        const uint64 offset = (uint64(string.base()) / sizeof(T)) % VECTOR_WIDTH_T;

        const uint64 aligned_begin = util::round_i( offset,                 VECTOR_WIDTH );
        const uint64 aligned_end   = util::round_z( offset + string.size(), VECTOR_WIDTH );

        return aligned_begin < aligned_end ?
            make_uint2( aligned_begin - offset, aligned_end - offset ) :
            make_uint2( string.size(), string.size() );
    }

    template <uint32 VECTOR_WIDTH_T>
    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const string_type& string,
        const uint32 offset,
        T*           vector)
    {
        const T* base_ptr = string.base() + offset;
        vector_load<VECTOR_WIDTH_T>( base_ptr, vector );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const string_type& string)
    {
        return range<VECTOR_WIDTH>( string );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const string_type& string,
        const uint32 offset,
        T*           vector)
    {
        load<VECTOR_WIDTH>( string, offset, vector );
    }
};

//
// --- vector_view< PackedStream > specialization---------------------------------------------------------------------
//

template <typename InputStream, typename Symbol, uint32 SYMBOL_SIZE_T, bool BIG_ENDIAN_T, typename IndexType>
struct vectorized_string< vector_view< PackedStream<InputStream,Symbol,SYMBOL_SIZE_T,BIG_ENDIAN_T,IndexType> > >
{
    typedef vector_view< PackedStream<InputStream,Symbol,SYMBOL_SIZE_T,BIG_ENDIAN_T,IndexType> >            string_type;
    typedef Symbol                                                                                          value_type;
    typedef IndexType                                                                                       index_type;
    typedef PackedStream<InputStream,Symbol,SYMBOL_SIZE_T,BIG_ENDIAN_T,IndexType>                           packed_stream_type;
    typedef InputStream                                                                                     storage_iterator;
    typedef typename packed_stream_type::storage_type                                                       storage_type;

    static const uint32 SYMBOL_SIZE  = SYMBOL_SIZE_T;
    static const uint32 SYMBOL_COUNT = 1u << SYMBOL_SIZE_T;
    static const uint32 VECTOR_WIDTH = packed_stream_type::VECTOR_WIDTH; 

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static uint2 range(const string_type& string)
    {
        const index_type offset = string.base().index();

        const index_type aligned_begin = util::round_i( offset,                 VECTOR_WIDTH );
        const index_type aligned_end   = util::round_z( offset + string.size(), VECTOR_WIDTH );

        return aligned_begin < aligned_end ?
            make_uint2( aligned_begin - offset, aligned_end - offset ) :
            make_uint2( string.size(), string.size() );
    }

    NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
    static void load(
        const string_type&  string,
        const uint32        offset,
        value_type*         vector)
    {
        const storage_iterator storage = string.base().stream();

        // find the proper word containing the vector we are after
        const index_type word_idx = (string.base().index() + offset) / VECTOR_WIDTH;

        const storage_type word = storage[ word_idx ];

        // unpack the entire word
        if (BIG_ENDIAN_T)
        {
            const uint32 SYMBOL_OFFSET = (VECTOR_WIDTH-1) * SYMBOL_SIZE;

            #pragma unroll
            for (uint32 j = 0; j < VECTOR_WIDTH; ++j)
                vector[j] = (word >> (SYMBOL_OFFSET - SYMBOL_SIZE * j)) & (SYMBOL_COUNT-1);
        }
        else
        {
            #pragma unroll
            for (uint32 j = 0; j < VECTOR_WIDTH; ++j)
                vector[j] = (word >> (SYMBOL_SIZE * j)) & (SYMBOL_COUNT-1);
        }
    }
};


} // namespace nvbio