import tensorflow as tf


def sparse_conv2d_matmul(x, w, blk_indices, strides, padding):
    """
    Performs 2D convolution using matrix multiplication on a sparse feature map.
    Naive python implementation of sparse convolution using gather and scatter.

    :param x:           [Tensor]  [N, H, W, C]. Input activation tensor, dtype float32.
    :param w:           [Tensor]  [I, J, C, K]. Convolution kernel, dtype float32.
    :param blk_indices: [Tensor]  [M, h, w, 3]. Block indices of rectangles.
    :param strides:     [list]    List of 4 int, convolution strides.
    :param padding:     [string]  `VALID` or `SAME`, padding method for sparse convolution.

    :return             [Tensor]  [N, H', W', C]. Convolution results.
    """
    blk_indices_ = tf.reshape(blk_indices, [-1, 3])
    blk_shape = tf.shape(blk_indices)
    ksize = tf.shape(w)

    # Calculate the block strides.
    bstrides = _calc_block_strides(blk_shape, ksize, strides)

    # Calculate the output size.
    x_shape = tf.shape(x)
    out_shape = calc_out_size_4d(x_shape, ksize, strides, padding)

    # Pad input.
    x_ = _pad_input(
        x, ksize, strides, padding, bsize=[1, blk_shape[1], blk_shape[2], 1], bstrides=bstrides)
